內容
給你一個式子X^2 ≡ 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。
輸入範例1:
5
輸入範例2:
8
輸入範例3:
15
輸出說明
第一行為一個整數n，代表共有多少組解。接下來的n 行則為所有滿足此式子的X，並由小到大輸出。
輸出範例1:
2
1
4
輸出範例2:
4
1
3
5
7
輸出範例3:
4
1
4
11
14
範例輸入
#1
15
範例輸出
#1
4 1 4 11 14
測資資訊：
記憶體限制：
64
MB
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1K
公開 測資點#2 (20%): 1.0s , <1K
公開 測資點#3 (20%): 1.0s , <1K
公開 測資點#4 (20%): 1.0s , <1K
公開 測資點#0 (20%): 1.0s , <1K
公開 測資點#1 (20%): 1.0s , <1K
公開 測資點#2 (20%): 1.0s , <1K
公開 測資點#3 (20%): 1.0s , <1K
公開 測資點#4 (20%): 1.0s , <1K
提示 ：
擴展歐幾里得算法(Extended Euclidean algorithm)
標籤:
出處:
九十六學年度高級中學資訊學科能力競賽決賽第6題
[管理者：
]
| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
沒有發現任何「解題報告」 |
|||||