全國(guó)賽noi選2007試題一

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

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

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

(3)程序文件擴(kuò)展名采用語言環(huán)境的默認(rèn)擴(kuò)展名。

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