hdu 1576（數論之擴展歐幾裡得）

分析：由 n = A % 9973，得 A = 9973 * x + n；

又 A % B == 0，則（9973 * x + n）% B == ans，所以 x = （ans * B -n）/9973；

其中X為整數。。

[cpp]
#include"stdio.h"  
#include"string.h"  
int main() 
{ 
    int T; 
    int i; 
    __int64 n,b; 
    scanf("%d",&T); 
    while(T--) 
    { 
        scanf("%I64d%I64d",&n,&b); 
        for(i=0;i<9973;i++) 
        { 
            if((b*i-n)%9973==0)break; 
        } 
        printf("%d\n",i); 
    } 
    return 0; 
} 

#include"stdio.h"
#include"string.h"
int main()
{
 int T;
 int i;
 __int64 n,b;
 scanf("%d",&T);
 while(T--)
 {
  scanf("%I64d%I64d",&n,&b);
  for(i=0;i<9973;i++)
  {
   if((b*i-n)%9973==0)break;
  }
  printf("%d\n",i);
 }
 return 0;
}