- #include
- #include
- #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<
- 求解最小正整数解的过程
- endl;
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-2158837.html