正题

题目链接:https://cometoj.com/problem/1479

---

题目大意

给出$n$求一个最小的$x(x>0)$满足
$$\left(\sum _{i=1}^{x}i\right)\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}n)$$

$1\le n\le 10^{12},1\le T\le 100$

---

解题思路

转成等比数列求和就是
$$\frac{i(i+1)}{2}\equiv 0(\mathrm{m}\mathrm{o}\mathrm{d}n)\Rightarrow i(i+1)=2kn$$

从里面获得一下信息，考虑枚举$2n$的所有约数$d$，那么我们有$xd\times y\frac{2n}{d}=2kn$。

也就是设$y\frac{2n}{d}=xd+1$，这个式子我们用$exgcd$求出最小解然后所有里面取最小的。

然后是一点优化，首先暴力枚举约数是$O(\sqrt{n})$的，我们可以质因数分解之后搜索就是$O({\sigma }_0(n))$的了。

然后因为$i$和$(i+1)$一定互质，所以$d$和$\frac{2n}{d}$不能有相同的质因子。

这样应该就能过了。

---

code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
const ll N=1e6+10;
ll T,n,ans,cnt,tot,pri[N/10],p[30];
bool v[N];
void Prime(){for(ll i=2;i<N;i++){if(!v[i])pri[++cnt]=i;for(ll j=1;j<=cnt&&i*pri[j]<N;j++){v[i*pri[j]]=1;if(i%pri[j]==0)break;}}return;
}
ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return a;}ll d=exgcd(b,a%b,x,y);ll z=y;y=x-(a/b)*y;x=z;return d;
}
void solve(ll x,ll f){if(x>tot){if(f==1||f==n)return;ll a=n/f,b=f,X,Y;ll d=exgcd(a,b,X,Y);Y=-Y;if(X<0){Y+=((-X+b-1)/b)*a;X+=((-X+b-1)/b)*b;}if(X>0){Y-=(X/b)*a;X-=(X/b)*b;}if(Y<0){X+=((-Y+a-1)/a)*b;Y+=((-Y+a-1)/a)*a;}ans=min(ans,min(X*a,Y*b));return;}solve(x+1,f);solve(x+1,f*p[x]);return;
}
signed main()
{Prime();scanf("%lld",&T);while(T--){scanf("%lld",&n);tot=0;n=n*2;ll x=n;ans=n-1;for(ll i=1;i<=cnt;i++){if(x%pri[i]==0){p[++tot]=1;while(x%pri[i]==0)p[tot]*=pri[i],x/=pri[i];}}if(x!=1){p[++tot]=x;}solve(1,1);printf("%lld\n",ans);}return 0;
}