题意

\(T\)组数据，求出最小的\(x\)使得\(n|\frac{x(x+1)}{2}\)
\(1\leq T\leq 100,1\leq n\leq 10^{12}\)

思路

原式\(\to 2n|x(x+1)\)。
设\(2n=A*B\)，且\(x+1=Ax_0,x=By_0\)
则题目所求即为\(Ax_0-By_0=1\)的解中，最小的\(By_0\)，食用扩欧即可。
时间复杂度\(O(T*(n的分解质因数复杂度+2^{n的不同质因子个数\leq 12}*log\ n))\)

代码

#include <cstdio>
#define int long long

int t, n, cnt, ans;
int prime[88001], v[1000001], a[13];

void calcPrime(int nn) {
    for (int i = 2; i <= nn; i++) {
        if (!v[i]) {
            v[i] = i;
            prime[++cnt] = i;
        }
        for (int j = 1; j <= cnt; j++) {
            if (prime[j] > v[i] || prime[j] > nn / i) break;
            v[i * prime[j]] = prime[j];
        }
    }
}

int exgcd(int a, int b, int &x, int &y) {
	if (!b) {
		x = 1;
		y = 0;
		return a;
	}
	int d = exgcd(b, a % b, x, y);
	int z = x;
	x = y;
	y = z - y * (a / b);
	return d;
}

signed main() {
	calcPrime(1000000);
	cnt = 0;
	scanf("%lld", &t);
	while (t--) {
		ans = 100000000000000, cnt = 0;
		scanf("%lld", &n);
		n *= 2;
		for (int i = 1; i <= 78498; i++)
			if (!(n % prime[i])) {
				int res = 1;
				while (!(n % prime[i]))
					n /= prime[i], res *= prime[i];
				a[++cnt] = res;
			}
		if (n > 1)
			a[++cnt] = n;
		int maxS = 1 << cnt, A, B;
		for (int s = 0; s < maxS; s++) {
			A = B = 1;
			for (int i = 1; i <= cnt; i++)
				((s >> i - 1) & 1) ? A *= a[i] : B *= a[i];
			int x0 = 0, y0 = 0;
			int d = exgcd(A, B, x0, y0);
			y0 = (y0 % A) + A % A;
			if (y0 > 0)
				y0 -= A;
			if (y0)
				ans = ans < -y0 * B ? ans : -y0 * B;
		}
		printf("%lld\n", ans);
	}
}