首页 > 代码库 > hdu 1576 A/B (求逆元)

hdu 1576 A/B (求逆元)

2024-08-02 23:51:17   211人阅读

题目链接

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
21000 5387 123456789
 
Sample Output
79226060
 
 1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <cmath> 6 #include <algorithm> 7 #define LL __int64 8 const int maxn = 1e3 + 10; 9 const int mo = 9973;10 using namespace std;11 12 void exgcd(LL a, LL b, LL &d, LL &x, LL &y)13 {14     if(!b) {d = a; x = 1; y = 0;}15     else{ exgcd(b, a%b, d, y, x); y -= x*(a/b); }16 }17 18 LL mo_reve(LL a, LL n)19 {20     LL x, y;21     LL d;22     exgcd(a, n, d, x, y);23     if(d==1) return (x%n+n)%n;24     else return -1;25 }26 27 int main()28 {29      int t, n, b;30      scanf("%d", &t);31      while(t--)32      {33          scanf("%d%d", &n, &b);34          int x = mo_reve(b, mo);35          printf("%d\n", n*x%mo);36      }37      return 0;38 }

 

hdu 1576 A/B (求逆元)


联系
我们