【NOIP訓練】【數論】超級計算機，noip數論

【NOIP訓練】【數論】超級計算機，noip數論

題目描述
有以下幾個問題：
1 給定正整數  求方程  的最小非負整數解。
2 給定正整數 求方程 的最小非負整數解。
3 給定正整數 求方程  在模  意義下解的數量。
4 給定正整數 求   的值。其中  是歐拉函數， 是莫比烏斯函數。
輸入格式
輸入文件共四行，按上述描述中四個問題的順序，給出每個問題。
第一行三個正整數   表示第一個問題，保證 。
第二行三個正整數 表示第二個問題，保證  。
第三行三個正整數  表示第三個問題，保證  為質數且  。
第四行三個正整數 表示第四個問題。
輸出格式
共四行每行一個整數，分別表示四個問題的答案。對於前兩個問題，若問題無解則輸出-1。對於第三個問題你只需輸出解的數量。
樣例數據
super.in
3 6 8
9 10 12
4 4 7
5 4 20

super.out
2
-1
2
4
數據范圍
20% 的數據：
60% 的數據：
100% 的數據：
評分方式
對於每個測試點:
• 第一個問題正確得 2 分。
• 第二個問題正確得 3 分。
• 第三個問題正確得 3 分。

題解

第一問：將式子化成  , 拓展歐幾裡得即可。

第二問： BSGS大步小步算法解高次同余方程。

詳情請見TonyFang博客：http://tonyfang.is-programmer.com/posts/178997.html

第三問：求出  的一個原根 ，可以求出 ，並設 , 則由費馬小定理可知，解該方程等價於解  所以實際上它是前兩個問題的組合應用。

第四問：Pollard Rho算法和Millar Rabin算法的應用。