思路：
我们很容易想到，题目要我们求得答案为
$$\frac{\left(1+x\right)x}{2}\%n==0$$
把除以2移项到右边
$$(1+x)x\%2n==0$$
我们再回顾扩展欧几里得(exgcd)的柿子
$$ax+by=gcd(x,y)$$
设$x+1=As$,$x=Bt$,其中$AB=2n$，那么$As-Bt=1.$

从而得到一个做法，枚举所有可能的A,B的组合，
用exgcd求解最小正数x=Bt更新答案。

在这个题目中，若gcd(A,B)=1，我们求As+Bt=1的一组特解(s,t)，从而令k=−t，(s,k)就是As−Bk=1的一组特解。我们要求x=Bk为最小正整数，而B是固定的正数，因而让k取最小正整数即可。显然地，若(s,k)是一组解，则u为整数时，(s+uB,k+uA)也是一组解。所以k<=0时取(k mod A ) +A，k>0时取(k mod A ) A即可。有些题目中gcd(A,B)!=1，此时用)A/gcd(A,B)和B/gcd(A,B)作为调整步长即可。

答案要求gcd(x,y)=1，就是x,y是互质的两个数，毕竟x,y是相邻的两个数。
考虑将2n质因数分解，分解出来的某一个质因数一定是全部属于x或y的。
否则两个数一定不是互质的。

#include <cstdio>
#include <iostream>
#define ll long long
//#pragma GCC optimize(2)
#define reg registerusing namespace std;const ll N = 1000000;ll T, n, p[N], ans, m, a[30], cnt;
bool S[N];void exgcd(ll a1, ll b1, ll &x, ll &y)
{if(!b1){x = 1, y = 0;return;}exgcd(b1, a1 % b1, x, y);ll t = x;x = y;y = t - a1 / b1 * y;
}void dfs(ll x, ll a1, ll b1)
{if(x > m){ll x1, y;exgcd(a1, b1, x1, y);y = -y;y %= a1;if(y <=0) y += a1;ans = min(ans, y * b1);return ;}dfs(x + 1, a1 * a[x], b1);dfs(x + 1, a1, b1 * a[x]);
}int main()
{for(reg ll i = 2; i <= N; i++){if(S[i]) continue;p[++cnt] = i;for(reg ll j = i + i; j <= N; j+=i)S[j] = 1;} scanf("%lld", &T);while(T--){scanf("%lld", &n);n *= 2;ans = n - 1;m = 0;for(reg ll i = 1; i <= cnt && p[i] <= n; i++){if(n % p[i] != 0) continue;a[++m] = 1;while(n % p[i] == 0) n /= p[i], a[m] *= p[i];}if(n > 1) a[++m] = n;dfs(1ll, 1ll, 1ll);printf("%lld\n", ans);}return 0;
}