题目来源：https://www.cometoj.com/contest/65/problem/C?problem_id=3684

题意：求k*(k+1)/2%n==0的最小k。

由k与k+1可以想到设置未知数：k+1=px,k=qy,可列得方程：px-qy=1，由此扩展欧几里得方程，

原方程为px*qy/2*n==(一个正整数)，考虑到时间复杂度的问题，可以将x,y先拆分为2*n的质因数 ，唯一分解定律拆分，最终化成质因子次幂的形式进行组合。

即x*y==2*n并且px-qy==1.

完了之后，需要对所有产生的质因数扫描一遍，比方说：有K个，那么x=1,2的时候则为依次类推，总情况数即他们相加的总和，直接二项式定理即为2的K次幂种情况，由2*3*5*7*11...找前十几个质数的乘积可以发现1e12不会超过12项，但是所有情况都需要计算一遍，用二进制搜索表示，1表示这一项质因数我乘在x里面。用二进制搜索的方式表示所有情况，判断一下min即可。

扩展欧几里德log（n）;

时间复杂度为预处理加内循环O(MAX+T*( 2^K*log n))

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cstdlib>
#include<vector>
#include<algorithm>
#include<queue>
#define MAX_len 50100*4
using namespace std;
typedef long long ll;
const int MAX=1e6+5;
int prime[MAX];
bool vis[MAX];
int tot=0;
void init()
{memset(vis,false,sizeof(vis));ll i,j;for(i=2;i<=MAX;i++){if(!vis[i]){vis[i]=true;prime[tot++]=i;for(j=i*i;j<=MAX;j+=i){vis[j]=true;}}}
}
ll exgcd(ll a,ll b,ll &x,ll &y)
{if(!b){x=1;y=0;return a;}ll g=exgcd(b,a%b,x,y);ll t1=x;x=y;y=t1-a/b*y;return g;
}
ll hh[MAX];
int main()
{init();int T;scanf("%d",&T);while(T--){int i,j;ll n;scanf("%lld",&n);n*=2;ll orz=n;int sum=0;for(i=0;i<tot&&prime[i]<=sqrt(n);i++){if(n%prime[i]==0){hh[++sum]=1;while(n%prime[i]==0){hh[sum]*=prime[i];n/=prime[i];}}}if(n!=1){hh[++sum]=n;}ll res=orz-1;for(i=1;i<(1<<sum);i++){ll x=1;for(j=0;j<sum;j++){if((1<<j)&i)x=x*hh[j+1];}ll y=orz/x;ll p,q;ll r=exgcd(x,-y,p,q);q/=r;x=abs(x/r);q%=x;if(q<=0)q+=x;res=min(res,q*(y));}printf("%lld\n",res);}	return 0;
}