Comet OJ - Contest #10 C.鱼跃龙门

传送门

题意：
求最小的\(x\)，满足\(\frac{x(x+1)}{2}\% n=0,n\leq 10^{12}\)。
多组数据，\(T\leq 100\)。

思路：

• 直接考虑模运算似乎涉及到二次剩余什么的，但比较复杂。
• 注意到比较特殊的就是，最后结果为\(0\)，那么我们就考虑将问题转化为整除。
• 所以式子等价于\(n|\frac{x(x+1)}{2}\)即\(2n|x(x+1)\)。
• 注意到\(n\)的范围，那么我们能\((O\sqrt{n})\)来枚举\(p,q\)，满足\(pq=2n\)。
• 那么就有\(pq|x(x+1)\)，不妨设\(x=qb,x+1=pa\)，那么就有\(pa-qb=1\)，现在就相当于知道\(p,q\)，求解最小的正数解\(a,b\)使得\(x\)最小。
• 显然这是经典的扩展欧几里得问题。

因为这个题卡常，所以我们将枚举改成枚举质因子，注意一下最后质因子分解的时候也要先把素数筛出来，不然也会T。
最后扩展欧几里得得到解的时候注意一下，我们可以选择正项或负项处理，我选择的是按负项处理直接得到答案。
(这点纠结了一会儿，就是处理的时候和位置无关，按正项处理不论处理哪一个都是第一项，负项处理不论哪一个都是第二项。)

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 35, MAX = 1e6 + 5;int T;
ll n;bool chk[MAX];
int prime[MAX], tot;void pre() {for(int i = 2; i < MAX; i++) {if(!chk[i]) {chk[i] = 1;prime[++tot] = i;for(ll j = 1ll * i * i; j < MAX; j += i) {chk[j] = 1;}}}
}void exgcd(ll a, ll b, ll &x, ll &y) {if(b == 0) {x = 1, y = 0;return ;}exgcd(b,a%b,x,y);ll z = x ;x = y;y = z - y * (a / b);
}int cnt;
ll tmp[N];ll calc(ll a, ll b) {ll x, y;exgcd(a, b, x, y);y = (y % a + a) % a;if(y * b >= 0) y -= a;return -y * b;//按负项处理
}ll dfs(int num, ll a, ll b) {if(num > cnt) return calc(a, b);return min(dfs(num + 1, a * tmp[num], b), dfs(num + 1, a, b * tmp[num]));
}int main() {ios::sync_with_stdio(false); cin.tie(0);pre();cin >> T;while(T--) {cin >> n;n <<= 1;cnt = 0;for(int i = 1; i <= tot; i++) {if(prime[i] > n) break;if(n % prime[i] == 0) {tmp[++cnt] = 1;ll now = prime[i];while(n % prime[i] == 0) {tmp[cnt] *= now;n /= prime[i];}}}if(n > 1) tmp[++cnt] = n;ll ans = dfs(1, 1, 1);cout << ans << '\n';}return 0;
}