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

代码如下  原理：    ax+cy=1 的解x即为a对c的乘法逆元 （%c情况下的乘法逆元）   详细可看我之前写的博客

#include<bits/stdc++.h>
using namespace std;
void exgcd(int a,int b,int& x,int& y){
	if(!b){
		x=1;y=0;
	}
	else{
		exgcd(b,a%b,y,x);
		y-=x*(a/b);
	}
}
int main(){
	int n,b,t,i,j,ans,x,y;
	while(cin>>t)
	while(t--){
		cin>>n>>b;
		exgcd(b,9973,x,y);         // gcd(b,9973)一定要为 1 即b和9973互质 
        if(x<0)                    // 乘法逆元为负数
		x=(x%9973+9973)%9973;
		cout<<(n*x%9973)%9973<<endl;
		
	}
	return 0;
}