【HDU 1576】 A/B

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

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=1576

题解：

很容易想到就是解线性方程 a*B+b*9973=n

很明显最小的正数a就是答案秒上exgcd

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<cmath>
 6 using namespace std;
 7 typedef long long ll;
 8 ll exgcd(ll a,ll b,ll &x,ll &y)
 9 {
10     if(!b)
11     {
12         x=1;y=0;
13         return a;
14     }
15     ll r=exgcd(b,a%b,x,y);
16     ll t=x;
17     x=y;
18     y=t-a/b*y;
19     return r;
20 }
21 void work(ll a,ll b,ll c)
22 {
23     ll x,y;
24     ll r=exgcd(a,b,x,y);    x*=c/r;
25     ll t=b/r;
26     if(t<0)t=-t;
27     x=(x%t+t)%t;
28     printf("%lld
",x);    
29 }
30 int main()
31 {
32     ll a,b;int T;
33     scanf("%d",&T);
34     while(T--)
35     {
36         scanf("%lld%lld",&a,&b);
37         work(b,9973,a);
38     }    
39     return 0;    
40 }