题目概述

求最小 $k$ 使得 $k(k+1)\over 2$ 是 $n$ 的倍数。

解题报告

AC的题太难了，我全都不会做​😭​。

移下项：$k(k+1)\equiv0\pmod{2n}$ 。

显然 $k$ 和 $k+1$ 是互质的，所以 $k$ 和 $k+1$ 提供的素因子是完全独立的。因此我们考虑将 $2n$ 分成 $A\times B$ ，只要存在 $A$ 和 $B$ 分别是 $k$ 和 $k+1$ 的因子，$k$ 就合法。

反过来，我们可以利用 $A$ 和 $B$ 求出 $k$ ：

$$ \begin{cases} k\equiv0\pmod{A}\\ k\equiv-1\pmod{B} \end{cases} $$

即求解 $Ax+By=B-1$ ，求出 $x_{min}$ 就可以得到 $k_{min}=Ax_{min}$ ，使用exgcd即可。

示例程序

#include<cmath>
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long double DB;typedef long long LL;

LL n,ans;

inline LL Mul(LL x,LL y,LL MOD) {return (x*y+MOD-(LL)((DB)x/MOD*y)*MOD)%MOD;}
LL exgcd(LL a,LL b,LL &x,LL &y){
    if (!b) {x=1;y=0;return a;}
    LL r=exgcd(b,a%b,y,x);y-=a/b*x;return r;
}
LL Solve(LL A,LL B,LL C){
    LL x,y,r=exgcd(A,B,x,y);if (C%r) return 1e18;
    LL T=B/r;x=Mul((C/r)%T,x%T,T);
    if ((DB)A*x>1e18) return 1e18;return A*x;
}
int main(){
    scanf("%lld",&n);n<<=1;ans=n-1;
    for (int S=sqrt(n),i=2;i<=S;i++)
        if (!(n%i)) ans=min(ans,Solve(n/i,i,i-1)),ans=min(ans,Solve(i,n/i,n/i-1));
    printf("%lld\n",ans);return 0;
}