HDU - 1576 - A/B 【数论+欧几里得】题解

逃离我推掉我的手 2021-07-24 14:45 433阅读 0赞

目录

      • 1.题目
      • 2.代码

1.题目

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

2.代码

  1. #include<iostream>
  2. #include<cstdio>
  3. const int mod=9973;
  4. using namespace std;
  5. int exGcd(int a,int b,int &x,int &y)
  6. { 
  7.     if(b==0)
  8.     { 
  9.           x=1;
  10.           y=0;
  11.           return a;
  12.     }
  13.     int g=exGcd(b,a%b,x,y);
  14.     int temp=x;
  15.     x=y;
  16.     y=temp-a/b*y;
  17.     return g;
  18. }
  19. int main()
  20. { 
  21.   int t,n,b;
  22.   cin>>t;
  23.   while(t--)
  24.   { 
  25.       cin>>n>>b;
  26.       int x=0,y=0;
  27.       int b1=exGcd(b,mod,x,y);
  28.       if(x<0) x+=mod;
  29.       int ans=(n*(x%mod)+mod)%mod;
  30.       cout<<ans<<endl;
  31.   }
  32.   return 0;    
  33. }

发表评论

表情：
评论列表 （有 0 条评论，433人围观）

还没有评论，来说两句吧...

相关阅读