A/B

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2613    Accepted Submission(s): 1917


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  
Author xhd  
Source HDU 2007-1 Programming Contest 题目分析：
因为9973是个素数，所以它和所有数互素，那么可以通过求取逆元求得(a/b)mod9973 = (a*inv(b)%9973＋9973)%9973
求取逆元采取的是拓展欧几里得算法
gcd(a,b) = ax + by;
若gcd(a,b) == 1 ，那么
1 = ax + by ,所以
(ax+by)%b = ax%b == 1
因为(m/a)%b = ( m/a*a*x)%b = 1;
所以x可以作为a的逆元，同理y是b的逆元，
拓展欧几里得算法中是是利用辗转相除逆向地递推出x,y的值，此处不做详解，具体过程就是解一个同余方程
#include #include #include #include #define MOD 9973 using namespace std; typedef long long LL; int t; LL n,b; LL exgcd ( LL a , LL b , LL &x , LL& y ) { if ( b == 0 ) { x = 1 , y = 0 ; return a; } LL r = exgcd ( b , a%b , x , y ); LL t = x; x = y; y = t - a/b*y; return r; } int main ( ) { scanf ( "%d" , &t ); while ( t-- ) { scanf ( "%lld%lld", &n , &b ); LL x , y; exgcd ( b , MOD , x , y ); printf ( "%lld " , (n*x%MOD+MOD)%MOD ); } }