hdu1576 A/B <数论>

链接:http://acm.hdu.edu.cn/showproblem.php?pid=1576

思路:由题意可知,一定有解,而且解空间很小, 故可以枚举;

M=9983, n=A%M gcd( b,M )==1, ans=(A?B)%M,

则 n == (ans*b)%M;

因为: A%M == (A/B*B)%M==(A/B%M * B%M)%M== (ans*B%M)%M;

View Code

 1 #include <iostream> 
 2 #include <cstdio> 
 3 #include <string.h> 
 4 using namespace std; 
 5  
 6 int main(){ 
 7     int T; 
 8     scanf("%d",&T); 
 9     while(T--){ 
10       __int64 n,b; 
11       int x; 
12       scanf("%I64d%I64d",&n,&b); 
13       for(int i = 0;i < 9973; ++i){ 
14           if(( b * i - n ) % 9973 == 0){ 
15             x = i; 
16             break; 
17           } 
18       } 
19       printf("%d\n",x);  
20     } 
21     return 0; 
22 }