[討論] 96年 全國資訊能力競賽 P6

[yuscvscv (小可魚)]

題目：

有個式子 X^2 % M == 1

給個M，求出X。

各數字的範圍(0 < X <= M <= 2147483647)

        輸入
        一個數字M

        輸出
        先輸出有幾組解，之後每行各輸出一組解

Sample 1

Input
5

Output
2
1
4


Sample 2

Input
8

Output
4
1
3
5
7


Sample 3

Input
15

Output
4
1
4
11
14



即使利用答案的對稱性將時間複雜度降到O(n/2)，
但有3組測資還是會超過限制的30s，然後TLE = =
(測資共5組 如下 僅供參考，Output很大就不PO了)
36
2147483647
2146654199
111546435
1509949440


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 118.171.147.78
推 scan33scan33:用中國餘式定理爆開？
→ yuscvscv:我先google一下那是什麼東西XD
→ yuscvscv:原來是那個喔 不過要怎麼爆?
→ yuscvscv:感覺不太像....
推 scan33scan33:http://www.numbertheory.org/php/squareroot.html
→ scan33scan33:x^2=1好像有比較簡單的解法......
→ yuscvscv:喔喔 太強大了~ 感謝
→ yuscvscv:經過學長的講解 用不定方程搞成O(sqrt(n))亂搜就OK了~
推 scan33scan33:喔喔！希望是有幫上忙就好了！:)
→ yuscvscv:他這個方法好像用來求一組解