老生常谈的问题 利用同余的思想 抽象出表达式 bx+9973y=n
然后用bx+9973y=1（题目给出了gcd(b,9973)=1） 求出基础解 y0
bx+9973y=n 的 基础解y=n*y0 接下来就是将y定位在0~9973这个区间里面、
#include <cstdio> #include <iostream> #include <string> using namespace std; typedef long long ll; ll exgcd(ll a,ll b,ll &x,ll &y) { if(b==0) { x=1; y=0; return a; } ll temp=exgcd(b,a%b,y,x); y-=(a/b)*x; return temp; } int main() { int t; cin>>t; while(t--) { ll n,b; cin>>n>>b; ll x,y; ll g=exgcd(b,9973,x,y); ll t=9973/g;// t为最小间距 x=(x*(n/g)%t+t)%t;// 求解最小正整数解的过程 cout<<x<<endl; } return 0; }
原文：http://www.cnblogs.com/z1141000271/p/7136004.html