正題

題目鏈接: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)?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; }

總結

以上是生活随笔為你收集整理的CometOJ-[Contest #10]鱼跃龙门【exgcd】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。