文章目錄

• • 題目：
  • 題解：
  • 代碼：

hdu 1576

題目：

要求(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

題解：

先了解一些概念：
費馬小定理：a^p?1≡1 (mod p) ，其中 gcd(a,p)=1 ，p為質數

逆元：對于a和p，若 a * inv(a) % p ≡ 1，則稱inv(a)為a%p的逆元。p為質數

代碼：

#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll mod=9973;ll poww(ll a,ll b) {ll ans=1;ll base=a;while(b){if(b&1!=0)ans=ans*base%mod;base=base*base%mod;b>>=1;}return ans%mod; } int main() {int t;cin>>t;while(t--){ll n,b;cin>>n>>b;//cout<<poww(2,3)<<endl;cout<<n*poww(b,mod-2)%mod<<endl;}return 0;} 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

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

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