一日之计在于晨

题目链接

戳这

\(Solution\)

要求最小的x使得\((t+a*x) \ mod \ m\)最小
令 \((t+a*x) \ mod \ m = b\)

根据不定方程的性质，这个不定方程要有解\(b-t\)要是\(gcd(a,m)\)的倍数
于是可以通过这个性质来求出最小的\(b\)
然后问题就转化为了 求这个不定方程的最小正整数解和最大非正整数解用一个\(exgcd\)就可以解决了

\(Code\)

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
const int N=2e5+10;
int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar();
    while(c>='0'&&c<='9') x=x*10+c-48,c=getchar();
    return f*x;
}
int exgcd(int a,int b,int &x,int &y){
	int d=a; 
    if(b==0) x=1,y=0; 
    else
		d=exgcd(b,a%b,y,x),y-=a/b*x;
	return d;
}
int n,t,a,m,ans;
signed main(){
    int T=read();
    while(T--){
        t=read(),a=read(),m=read();
        int Gcd=gcd(a,m);
        int X=(1-t)/Gcd;
        int B=X*Gcd+t,x,y;
        int b=m,c=B-t;
        int d=exgcd(a,b,x,y);
        x*=c/d,y*=c/d;
        int p=b/d,q=a/d,k;
        if(x<0) {
            if((1-x)%p==0) k=(1.0-x)/p;
            else k=(1-x)/p+1;
            x+=p*k,y-=q*k;
        }
        else if(x>=0)k=(x-1)/p ,x-=p*k,y+=q*k;
        if(abs(x-m/Gcd)<x) cout<<abs(x-m/Gcd)<<"\n";
        else cout<<x<<"\n";
    }
}