---

6. X平方 ≡ 1 (mod M)

問題敘述：
給你一個式子X平方 ≡ 1 (mod M) 和M ( 0＜X≦M )，請找出所有符合這個式子
的X。
例如：M=5，則X 可以等於1 或4；M=8 時，X 可以等於1, 3, 5, 7。
請你寫一個程式，針對每一個M，輸出能滿足這個式子的X。
輸入說明：
每一個測試檔裡有一個整數即為M，你可以假設M 不會大於2147483647。
輸出說明：
第一行為一個整數n，代表共有多少組解。
接下來的n 行則為所有滿足此式子的X，並由小到大輸出。
輸入範例1:
5
輸出範例1:
2
1
4
輸入範例2:
8
輸出範例2:
4
1
12
3
5
7
輸入範例3:
15
輸出範例3:
4
1
4
11
14

這是我今年參加全國賽的題目,可是怎麼享就是想不出一個快數的解法,他題目限定一定要十秒內算出,可是我寫出來後算最大數要花到超過60秒,不知各位高手們有沒有甚麼快速的解法.  

---

先建立一張平方表

table[i] = {1 4 9 16 .... 2147395600(46340^2) } (for i = 1 ~ 46340)

然後就從表裡拿出資料試table[i]，若是table[i] mod m ≡ 1，就輸出i

不曉得這樣會不會太慢，有公佈測資嗎？ 

 

---

就算見表也要到2147483647 ( 0＜X≦M ),基本上陣列已經太大建立不出,而且光是讓系統從1建檔建到2147483647基本上時間一定不夠,需要160s 

---

不用建那麼大，實際上只有for i = 1 ~ 46340

table[1]=1^2=1

table[2]=2^2=4

table[3]=3^2=9

...

table[46340]=46340^2= 2147395600

 

---

為什麼只用求 1 ~ 46340 ,這又不是在求質數 

---

參考看看

#include <iostream>
 using namespace std;
 
 #define MAXSIZE	46340
 int table[MAXSIZE+1];
 int ans[MAXSIZE],count;
 
 void maketable(){
 	for(int i=1;i<=MAXSIZE;i++)
 		table[i]=i*i;
 }
 
 int main(){
 	int m;
 	int i;
 
 	maketable();
 	while(cin >> m){
 		count=0;
 		for(i=1;i<=MAXSIZE;i++){
 			if(i>m) break;
 
 			if(table[i]%m==1) ans[count++]=i;
 		}
 
 		cout << count << endl;
 		for(i=0;i<< ans[i] << endl;
 	}
 
 	return 0;
 }
 

 

---

赫然發現我少考慮另一部分

想得太簡單了 

 

---

這題你不是在NPSC補完計畫問過了.....

http://www4.tcgs.tc.edu.tw/0/view.asp?b=2100&r=29524