HDU 1576
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
submit
这道题的大致意思题目已经写得很清楚了，就是给你n（n=A%9973）和B，让你去求（A/B）%9973的值。
思路：假设（A/B）%9973=x
=>9973k+x=A/B
=>9973kB+Bx=A
=>Bx%9973=A%9973(左右两项同时mod 9973)
=>Bx%9973=n (题目已知)
=>Bx=9973y+n
=>Bx-9973y=n
到这里就是扩展欧几里得算法（注意求出来的x有可能是负数，所以我们需要把x进行如下操作 x=(x%9973+9973)%9973，同时需要注意扩展欧几里得求得的是 Ax+By=gcd(A,B)的解，所以最后我们要将x乘上n才可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
const int mode=9973;
void extend_gcd(int a,int b,int &x,int &y){if(b==0){x=1,y=0;return;}extend_gcd(b,a%b,x,y);int tmp=x;x=y;y=tmp-(a/b)*y;
}
int main(){int t;cin>>t;while(t--){int x;int y;int n,B;cin>>n>>B;extend_gcd(B,9973,x,y);x=(x%mode+9973)%mode;cout<<(x*n)%mode<<endl;}
}
道阻且长
自己选的路 跪着也要走完