题目

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

题意

求出b和9973的最大公约数 a 乘以最大公约数 再取余就可以了，用辗转相除法总是re，所以用了扩展欧几里得

code

#include<stdio.h>
#include<string.h>
long long exgcd(long long a,long long b,int &x,int &y)
{
	if(b==0)
	{
		x=1,y=0;
		return 0;
	}
	long long r=exgcd(b,a%b,x,y);
	long long t;
	t=y;
	y=x-(a/b)*y;
	x=t;
	return r;
}
int main()
{
	long long t,m,n;
	int x,y;
	scanf("%lld",&t);
	while(t--)
	{
		scanf("%lld%lld",&m,&n);
		exgcd(n,9973,x,y);
		x*=m;
		x=(x%9973+9973)%9973;
		printf("%d\n",x%9973);
	}
	return 0;
}