HDU1576（欧几里得拓展）

思路：

1. 欲求:A/B%9973
2. 令 A/B==X 则A==X*B
3. 已知:B,N 且N==A%9973
4. 因为 gcd(B,9973)==1
5. 则 Bx1+9973y1==gcd(B,9973)==1…(1)
6. 又 N=A-A/9973*9973 == BX+9973(-A/9973)…(2)
7. 令Y==-A/9973
8. 则(2):BX+9973Y==N
9. 由(1):Bx1*N+9973y1*N==1*N…(3)
10. 所以 X==x1*N
11. 而 x1可以通过欧几里得拓展定理求得特解
12. 再将这个通解化为正数范围内就能够解决问题

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;
#define maxn (int)1e5+10
#define INF 1000000000

typedef long long ll;
typedef double db;

ll e_gcd(ll A,ll B,ll C[])
{
    if(B==0)
    {
        C[0]=1;
        C[1]=0;
        return A;
    }
    ll res=e_gcd(B,A%B,C);
    ll t=C[0];
    C[0]=C[1];
    C[1]=t-A/B*C[0];
    return res;
}

int main()
{
    ll B,N,C[2],T,result;
    cin>>T;
    while(T--)
    {
        cin>>N>>B;
        e_gcd(B,9973,C);
        result=(C[0]%9973+9973)%9973; //让该解在正数mod的范围内
        cout<<(result*N)%9973<<endl;
    }
    return 0;
}

PS：如果知道A、B要求通解的话，只需在循环中C[0]+nB,C[1]-nA.