2007年安聯杯安徽省青少年信息學奧林匹克競賽一試試題安徽淮北2007.4.212007年安徽省安聯杯信息學奧林匹克競賽AHOI2007第一試比賽時間：2007年4月21日8:00至11:00題目名稱密碼箱宮殿大門燈陣可執行文件名box.exeDoor.exelight.exe輸入文件名box.inDoor.inlight.in輸出文件名box.outDoor.outlight.out試題類型傳統型傳統型傳統型滿分100100100是否有部分分否否否時限1秒1秒2秒注意事項務必看清題目，嚴格按照所要求的格式輸入、輸出。在調試程序時請先使用題目中的示例數據，然后再自行設計多組測試數據進行調試。測試有嚴格的時間限制，請盡可能優化算法。命名規則：

(1)每題都規定了該題的英文名稱。

(2)程序文件和數據文件的主文件名都是該題的英文名字。

(3)程序文件擴展名采用語言環境的默認擴展名。

(4)數據文件都是文本文件，輸入和輸出文件的擴展名分別是.in和.out。程序應從輸入文件讀取數據，并嚴格地按照規定的輸出格式將結果輸出到輸出文件中。輸入數據文件和輸出數據文件都與程序在同一個目錄中，由于程序所在目錄是不確定的，因此不允許在程序中含有盤符信息和任何形式的路徑信息。選手在競賽結束時應在硬盤指定位置建立以參賽號命名的文件夾，并將所完成各題的源程序文件和編譯所產生的可執行文件(即擴展名為.exe的文件)拷貝到該文件夾中。題目密碼箱（Box）在一次偶然的情況下，小可可得到了一個密碼箱，聽說里面藏著一份古代流傳下來的藏寶圖，只要能破解密碼就能打開箱子，而箱子背面刻著的古代圖標，就是對密碼的提示。經過艱苦的破譯，小可可發現，這些圖標表示一個數以及這個數與密碼的關系。假設這個數是n，密碼為x，那么可以得到如下表述：密碼x大于等于0，且小于n，而x的平方除以n，得到的余數為1。小可可知道滿足上述條件的x可能不止一個，所以一定要把所有滿足條件的x計算出來，密碼肯定就在其中。計算的過程是很艱苦的，你能否編寫一個程序來幫助小可可呢？（題中ｘ，ｎ均為正整數）輸入：輸入文件只有一行，且只有一個數字n(1<=n<=2,000,000,000)。輸出：你的程序需要找到所有滿足前面所描述條件的x，如果不存在這樣的x，你的程序只需輸出一行“None”(引號不輸出)，否則請按照從小到大的順序輸出這些x，每行一個數。樣例：輸入：12輸出：15711宮殿大門（Door）密碼箱終于被打開了，里面真的有一張古代的藏寶圖，這是一個古代君主留下來的寶藏，藏在一個至今沒有人發現的地下宮殿中，要取得寶藏必須破解重重機關。小可可毫無畏懼，作為他的好朋友，你們就這樣開始了尋寶旅程。經過千辛萬苦，你們來到了地下宮殿的入口，遇到了第一個麻煩。宮殿的大門怎么都無法打開。小可可仔細觀察以后發現，大門的左半扇門上有一些數字，像一個n*n的矩陣般排列，右半扇門對應的位置上也有同樣的n*n數字排列，不過數字均為0，這些0都可以通過機關變成其他的數字，甚至是負數，但是排列方式不會變。小可可仔細研究了藏寶圖，發現要打開這扇門必須要將右半扇門上的數字按照一定的規律進行改變。若假設左邊n*n矩陣為A，改變后的右邊n*n矩陣為B，這個規律就是：它們的乘積C矩陣：Ci,j=，且C=A*B=En其中En為：Ei,j=0（若i不等于j），Ei,j=1（若i等于j）。即，Ｂ為Ａ的逆矩陣。你能幫助小可可打開這扇門嗎？輸入：輸入文件的第一行為一個整數n(1<=n<=200).以下n行，每行n個數，按照行主序給出A的每個元素，即：A1,1,A1,2,……，A1,n，A2,1,A2,2,……，A2,n，……An,1,An,2,……，An,n.輸出：輸出文件為n行，每行n個整數，且在-2,000,000,000與2,000,000,000之間，每兩個相鄰的數用一個空格隔開，即按照行主序表示的矩陣B。輸入數據保證這個矩陣B存在，且B的每個元素為一個整數，并且在-2,000,000,000與2,000,000,000之間。特別提示：由于測試采取文件比對方式，所以這里約定，如果結果中某個數為0，則應輸出0，而不是-0。樣例：輸入：31-11012104輸出：44-323-2-1-11燈陣（Light）宮殿的大門打開了，里面漆黑一片，藏寶圖上記載，必須要點亮燈陣，宮殿內的各種陷阱才會關閉，才能進入宮殿深處，否則每一步都有極大的危險。這個燈陣是由很多盞油燈組成，它們排成長長的一行。這些油燈經過巧妙的設計，有很多種型號，每種型號都有專用的點燈工具。假設每盞燈都有一個類型編號p（1<=p<=2,000,000,000）。那么點燈工具也有不同的編號s（1<=s<=2,000,000,000）。每盞燈只能被與自己編號相同的點燈工具點燃，例如1號類型的燈只能被編號為1的點燈工具點燃。燈陣旁邊就有古代的點燈器，它是一個類似樹杈的東西，后端一個粗把手，前端有一些分叉。只不過前端的分叉可以任意增加和減少，每個分叉末端都必須正好安裝一種點燈工具，這樣就可以同時點燃數個燈，但是點燈工具一旦安裝上就無法去掉，所以分叉的個數與點燈工具的安裝都要經過精細的計算。經過現場仔細的觀察和對藏寶圖的研究，小可可了解到燈的分布情況與點燃的方式為：所有燈按順序排成一行，位置從左到右分別為1,2,3,……,n，稱為1號位、2號位等等，每兩條相鄰的燈的間隔是相等的，可以有重復型號的燈。點燈器分叉的末端在一條直線上，上面必須掛m個點燈工具，每兩個相鄰的點燈工具的間隔相等，且等于每兩條相鄰的燈的間隔；從最左邊的燈開始，把點燈器上最左邊的點燈工具與最左邊的燈對齊，分叉末端點燈工具的排列方向與燈排列的方向相同，且必須保證所有點燈工具的編號與那個要點燃的燈的編號相等；然后就可以點燈了。燈一旦點燃就不會熄滅。點燈的過程就是從最左邊開始，不斷向右走（從不往回走，也不掉轉點燈器的方向），尋找下一個點燈的位置。必須仍然保證所有點燈工具的編號與要點燃的燈的編號相等，而且每個點燈工具下都必須有燈；一定要保證所有的燈都被點燃（當然，可能有一些燈被點了多次）。只有這樣，燈陣才算被真正點亮，也才能進行下一步探寶。燈陣旁邊有足夠多的各種型號的點燈工具。如果點燈器前端的分叉數量大于等于1且小于等于n，那么需要多少個分叉能夠保證成功點亮燈陣呢？小可可想麻煩你來幫他計算所有可能的情況，他會根據你的計算最終確定合適的點燃燈陣的方案。用于安裝點燈工具用于安裝點燈工具點燈器示意圖輸入：輸入