AB

H. A/B

Time Limit: 1000ms Memory Limit: 32768KB 64-bit integer IO format:      Java class name: Submit Status

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

 

Input

输入多组数据。 每组数据有两个数n(0 <= n < 9973)和B(1 <= B <= 10^9)。

Output

对应每组数据输出(A/B)%9973。

Sample Input

1000 53 87 123456789

Sample Output

7922 6060 同于定理 #include<stdio.h> int main() { long long int m; int n,h; while(scanf("%d%lld",&n,&m)!=-1) { long long int y=0; for(int i=1;i<=10000;i++) { y=i*m; if(y%9973==1) { h=i; break; } } long long int g; g=(h*n)%9973; printf("%lld\n",g); } }