网站开发前景好吗,做微博网站,网页制作的公司排名,沈阳室内设计公司排名文章目录题目#xff1a;题解#xff1a;代码#xff1a;hdu 1576题目#xff1a; 要求(A/B)%9973#xff0c;但由于A很大#xff0c;我们只给出n(nA%9973)(我们给定的A必能被B整除#xff0c;且gcd(B,9973) 1)。 Input 数据的第一行是一个T#xff0c;表示有T组数据。…
文章目录题目题解代码hdu 1576题目 要求(A/B)%9973但由于A很大我们只给出n(nA%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 123456789Sample Output
7922
6060题解
先了解一些概念 费马小定理ap−1≡1 (mod p) 其中 gcd(a,p)1 p为质数
逆元对于a和p若 a * inv(a) % p ≡ 1则称inv(a)为a%p的逆元。p为质数
代码
#includebits/stdc.h
using namespace std;
typedef long long ll;
const ll mod9973;ll poww(ll a,ll b)
{ll ans1;ll basea;while(b){if(b1!0)ansans*base%mod;basebase*base%mod;b1;}return ans%mod;
}
int main()
{int t;cint;while(t--){ll n,b;cinnb;//coutpoww(2,3)endl;coutn*poww(b,mod-2)%modendl;}return 0;}
