problem
实际上就是对于给定的$n$求一个最小的$x$满足$\frac{x(x+1)}{2}=kn(k\in N^*)$。
solution
对上面的式子稍微变形可得$x(x+1)=2kn$。因为$x$与$(x+1)$互质，所以将$n$质因数分解后，同种质因子肯定都位于$x$或$(x+1)$中。$10^{12}$以内的整数质因数分解后种类不超过$13$种，所以可以暴力枚举每种质因子属于$x$还是$x+1$。
然后分别得到$a$和$b$。下面要使得$bx=ay+1$。扩展欧几里得求解即可。
PS
本题时限$0.5s$,每次询问都$\sqrt{n}$质因数分解是会$TLE$的。所以先预处理质数。然后进行质因数分解。
code
//@Author: wxyww
#include<cstdio>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<vector>
#include<ctime>
#include<cmath>
#include<map>
#include<string>
using namespace std;
typedef long long ll;
const int N = 5000010;
ll read() {
ll x = 0,f = 1; char c = getchar();
while(c < '0' || c > '9') {if(c == '-') f = -1;c = getchar();}
while(c >= '0' && c <= '9') {x = x * 10 + c - '0',c = getchar();}
return x * f;
}
ll dis[N];
int prmjs,vis[N];
ll n;
ll js,cnt[15];
void fj(ll x) {
for(int i = 1;dis[i] * dis[i] <= x;++i) {
if(x % dis[i] == 0) {
cnt[++js] *= dis[i];
x /= dis[i];
}
while(x % dis[i] == 0) x /= dis[i],cnt[js] *= dis[i];
}
if(x != 1) cnt[++js] = x;
}
ll ans;
ll exgcd(ll a,ll b,ll &x,ll &y) {
if(b == 0) {
x = 1,y = 0;return a;
}
ll tmp = exgcd(b,a % b,x,y);
ll t = x;
x = y; y = t - a / b * y;
return tmp;
}
int main() {
int T = read();
for(int i = 2;i <= 2000000;++i) {
if(!vis[i]) dis[++prmjs] = i;
for(int j = 1;j <= prmjs && 1ll * dis[j] * i <= 1000000;++j) {
vis[dis[j] * i] = 1;
if(i % dis[j] == 0) break;
}
}
while(T--) {
n = read() * 2;
js = 0;
for(int i = 1;i <= 14;++i) cnt[i] = 1;
fj(n);
ans = n * 2;
ll m = 1 << js;
for(int i = 0;i < m;++i) {
ll now = 1;
for(int j = 0;j < js;++j) if(i >> j & 1) now *= cnt[j + 1];
ll x,y;
exgcd(now,n / now,x,y);
y = y % now;
if(y >= 0) y -= now;
ans = min(ans,n / now * -y);
}
printf("%lld\n",ans);
}
return 0;
}