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秒,不知各位高手們有沒有甚麼快速的解法.