HDU 1576 A/B

题意：

Problem Description

要求(A/B)%9973，但由于A很大，我们只给出n(n=A%9973)(我们给定的A必能被B整除，且gcd(B,9973) = 1)。

想法：设X=(A/B)%9973 ==> A/B=k*9973+X (k为正整数) ==> A=k*9973*B+X*B

又因为n=A%9973 ==> A=p*9973+n (p为正整数) ==> p*9973+n=k*9973*B+X*B ==> p*9973-k*9973*B=X*B-n 从这个式子可以看出左半边可以被9973整除，所有可得(X*B-n)%9973=0;

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int n;

unsigned long long b;

int main()

{

int t;

scanf("%d",&t);

while(t--)

{

scanf("%d%lld",&n,&b);

int res;

for(int i=0;i<=9973;i++)

{

int kk=(i*(b%9973)-n+9973)%9973;

if(kk==0)

{

res=i;

break;

}

}

printf("%dn",res);

}

return 0;

}