A/B

Time Limit: 1000/1000 MS (Java/Others)????Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1369????Accepted Submission(s): 1045

?

Problem Description

要求(A/B)%9973，但由于A很大，我們只給出n(n=A%9973)(我們給定的A必能被B整除，且gcd(B,9973) = 1)。

?

?

Input

數據的第一行是一個T，表示有T組數據。
每組數據有兩個數n(0 <= n < 9973)和B(1 <= B <= 10^9)。

?

?

Output

對應每組數據輸出(A/B)%9973。

?

?

Sample Input

?

2 1000 53 87 123456789

?

Sample Output

?

7922 6060

思路：由gcd(B,9973)=1可知，B與9973互質，且為質數，因此可以用費馬小定理來求出B對9973的乘法逆元；

（A/B）%mod==（A*B的逆元）%mod.

代碼：

#include <iostream> using namespace std; typedef long long ll; int mod=9973; ll quickpow(ll a,ll b) {ll res = 1;a = a % mod;while(b){if(b & 1) res = res * a % mod;a = a * a % mod;b >>= 1;}return res; } int main() {int t,n,b,ans;cin>>t;while(t--){cin>>n>>b;ans=quickpow(b,mod-2);cout<<ans*n%mod<<endl;}return 0; } ?

?

?

?

總結

以上是生活随笔為你收集整理的HDU1576 A/B 费马小定理的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。