【Comet OJ - Contest #10】鱼跃龙门(扩展欧几里得思维)

题目

题目大意：T组查询，每次询问一个满足x*（x + 1）% （2n) = 0的最小正整数。

T<=100, n<=1e12

思路：

x -> x*(x + 1) % (2n) == 0

转换成 a | 2n, b = 2n | a;

假设 ap = x + 1, x = bq。

联立得到ap - bq = 1的最小正整数解bq。

由于该方程有解的条件的gcd(a, b) = 1.

枚举 时只用枚举a的每个质因子要不要给 2n。

先预处理1e6内的素数，假设为D， 2n的不同种类质因子个数为K。

求解一次扩欧方程时间复杂度为logn

整体时间复杂度

T（n） = O(T(D + 2^K * log n)

AC code;

/*
find min x -> x*(x + 1) % (2n) == 0
-> suppose a | 2n, b = 2n | a;
-> suppose ap = x + 1, x = bq,
->  
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
const int maxn = 1e6 + 10;
bool isprime[maxn];
int cntp, prime[maxn];
void init(){
    memset(isprime, 1, sizeof(isprime));
    cntp = isprime[0] = isprime[1] = 0;
    for(int i = 2; i < maxn; ++i){
        if(isprime[i]){
            prime[++cntp] = i;
        }
        for(int j = 1; j <= cntp && i * prime[j] < maxn; ++j){
            isprime[i * prime[j]] = 0;
            if(i % prime[j] == 0) break ;
        }
    }
}
ll fac[50];
void getfac(ll n){
    fac[0] = 0;
    for(int i = 1; i <= cntp && prime[i] <= n; ++i){
        if(n % prime[i] == 0){
            fac[++fac[0]] = 1;
            while(n % prime[i] == 0) n /= prime[i], fac[fac[0]] *= prime[i]; 
        }
    }
    if(n > 1) fac[++fac[0]] = n;
}
ll exgcd(ll a, ll b, ll &x, ll &y){
    if(!b) return x = 1, y = 0, a;
    ll d = exgcd(b, a % b, x, y);
    ll t = x;
    x = y, y = t - (a / b) * y;
    return d;
}
ll ans;
void dfs(int cur, ll a, ll b){
    if(cur == fac[0] + 1){
        ll x, y;
        exgcd(a, b, x, y);
        // cout << "---" << a << " " << b << " " << y << endl;
        y =  -y % a;
        if(y <= 0) y += a;
        ans = min(ans, y * b);
        return ;
    }
    dfs(cur + 1, a * fac[cur], b);
    dfs(cur + 1, a, b * fac[cur]);
}
int main(){
    init();
    int T;
    scanf("%d", &T);
    while(T--){
        ll n;
        scanf("%lld", &n);
        if(n == 1){
            puts("1"); continue ;
        }
        n *= 2;
        getfac(n);
        ans = INF;
        dfs(1, 1, 1);
        printf("%lld\n", ans);
    }
    return 0;
}