Comet OJ - Contest #10 C-鱼跃龙门 （扩展GCD+暴力枚举）

ax+ ny= b 方程最小正整数解
ax≡b(mod n) 求逆元原理（同余方程）
ax+by=gcd(a,b) （a,b互质才有解）

#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#define IOS ios::sync_with_stdio(0); cin.tie(0);
#define mp make_pair
#define Accept 0
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
const double Pi = acos(-1.0);
const double esp = 1e-9;
const int inf = 0x3f3f3f3f;
const int maxn = 1e5+7;
const int maxm = 1e6+7;
const int mod = 1e9+7;
const int MAXL = 1e6+7;

int prim[MAXL];
int cnt;
ll fac[MAXL];
int vis[MAXL];
int cur;
ll mx;//该数质因子的幂的最大次数 

int getPrime(){
    int i,j;
    int cnt = 0;
    memset(vis,0,sizeof(0));
    vis[0] = vis[1] = 1;
    for(i=2;i<=MAXL;++i)
    {
        if(!vis[i]) vis[i]= prim[cnt++]= i;
        for(j=0;j<cnt&&i*prim[j]<=MAXL;++j){
            vis[i*prim[j]] = 1;
            if(i%prim[j]==0) break;
        }
    }
    return cnt;
}
ll exgcd(ll a,ll b,ll &x,ll &y) {
    if(b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    ll d = exgcd(b,a%b,x,y),temp = x;
    x = y;
    y = temp-a/b*y;
    return d;
}
int getFactor(ll n,int cnt){
    int cur = 0;
    for(int i=0;i<cnt;i++){
        if(n==1) break;
        if(n%prim[i]==0){
            fac[cur] = 1;
            while(n%prim[i]==0){
                n /= prim[i];
                fac[cur] *= prim[i];
            }
            cur++;
            mx = max(mx,fac[cur]);
        }
    }
    if(n>1) fac[cur++] =n;return cur;
}

ll solve(ll n){
        ll ans = n<<1;
    //有那么多个互质质因子组成种可能 
    for(int i=1;i<(1<<(cur));i++){
        ll a = 1,b;
        for(int j=0;j<(cur);j++){
            if(i&(1<<j)) a *= fac[j];
        }
        b = 2*n /a;
        ll x,y;
        exgcd(a,b,y);
        ans=min(ans,min(-((x%b+b)%b-b)*a,-((y%a+a)%a-a)*b));
//        exgcd(a,y);
//        ll xx=x,yy=y;
//        if(x>0){
//            x = xx%b;
//            y += (xx-x)/b*a;
//        }else{
//            y = yy%a;
//            x += (yy-y)/a*b;
//        }
//        ans = min(ans,min(abs(a*x),abs(b*y)));    
    }
    return ans;
}
int main(){
    int T;
    cnt = getPrime();
    cin>>T;
    //设x+1 = ap,x = bq; 可得ap-bq = 1;
    //求bq的最小解,exgcd();
    while(T--){ 
        ll n; scanf("%lld",&n);
        n <<= 1 ;
        cur = getFactor(n,cnt);
        ll ans = solve(n/2); 
        printf("%lldn",ans);
    }
}