题目大意： 给你一个 n ，让你求出最小的正整数 x 使得 x * (x + 1) / 2 % n == 0 ，即 x * (x + 1) % 2n == 0 。
分析：
1、由于 x * (x + 1) 为 2n 的倍数，故分离出它们各自的某个因数使得 k1 * k2 == 2n 。
则令 k2 * b = x + 1 ，k1 * a = x 。则有：
2、显然上述 一式 为不定方程，倘若先将负号放到 a 里面，则系数分别为 k2 与 k1 ，有解 b 与 a 当且仅当 gcd(k2，k1) | 1 ，故 k2 与 k1 必须互质。
3、故结合二式，求得 k1 与 k2 互斥时的解即可。很直接的做法是 枚举根号 2n 中的 k1 与 k2 ，判断是否互质，但由于本题时限仅为 500ms，会导致超时。
4、分析一下，如果 k1 与 k2 为 2n 的因数且它们互质，当且仅当 k1 与 k2 各不含有相同的 2n的质因子，故可枚举 2n 的所有质因子，将某个或某些质因子只放在
k1 或 k2 当中，那么它们就互质了。
比如 36 质因式分解为：2 * 2 * 3 * 3 ，质因子为 2 和 3，可以将 2 全部归于 k1 ，剩下的全部归于 k2 ，那么 k1 = 2 * 2 = 4 ，k2 = 3 * 3 = 9 ，它们互质。
注意：
对一式扩欧求解时，需要注意他的第二项系数为负的，之前说负号先给到 a ，然后再以系数为 k2 、 k1 时求得解，得出来的解 a 按理是需要取相反数的。
其次，由于得出来的 -a 不一定是最小正整数解，故需要对 k2/g 取余，这里的 g 为 1 ，故对 k2 取余即可。若结果为负数，需要加上 k2/g 变为最小正整数解。
（该题求的是不定方程的第二项 y ，若要求不定方程的第一项 x 的最小正数解，需要对 (第二项的系数)/g 取余得到，详见可结合我的 另一篇文章 ，最底下有方程组与解释 ）
代码如下：
#include<iostream> #include<algorithm> #include<map> using namespace std; #define INF 1e17 #define maxn 1000008 typedef long long ll; int cnt,tot; bool vis[maxn]; int t; int prime[maxn]; ll n,ans; ll m[1000008]; void biao() { vis[0]=vis[1]=true; for(int i=2;i<=1000000;i++){ if(!vis[i]) prime[++cnt]=i; for(int j=1;j<=cnt&&i*prime[j]<=1000000;j++){ vis[i*prime[j]]=true; if(i%prime[j]==0) break; } } return; } ll exgcd(ll a,ll b,ll &x,ll &y){ if(!b){ x=1; y=0; return a; } else{ ll g=exgcd(b,a%b,x,y); ll temp=x; x=y; y=temp-(a/b)*y; return g; } } void dfs(int i,ll k1,ll k2){ if(i==tot+1){ ll a,b; exgcd(k2,k1,b,a); a=-a; a%=k2; if(a<=0) a+=k2; ans=min(ans,k1*a); return; } dfs(i+1,k1*m[i],k2),dfs(i+1,k1,k2*m[i]); return; } int main() { biao(); scanf("%d",&t); while(t--) { tot=0; ans=INF; scanf("%lld",&n); n*=2ll; for(int i=1;i<=cnt&&prime[i]*prime[i]<=n;i++){ if(n%prime[i]==0){ ll res=1; while(n%prime[i]==0){ n/=prime[i]; res*=prime[i]; } m[++tot]=res; } } if(n!=1) m[++tot]=n; dfs(1,1ll,1ll); printf("%lld ",ans ); } }