## 【HDU-5976】Detachment【二分+模逆元（费马小定理+同余式解法）】

【HDU-5976】Detachment【二分+模逆元（费马小定理+同余式解法）】

```#include <iostream>

using namespace std;

typedef long long LL;
const int SIZE = 5e4;
const int LIM = 1e5;
const LL MOD = 1e9 + 7;
const LL MOD2 = 1e9 + 5;
LL pre[SIZE];
LL fractorial[SIZE];
// modula reverse identity element
LL mr[SIZE];

LL fastPow(LL base, LL p) {
LL ret = 1;
while (p) {
if (p & 1) ret = ret * base % MOD;
p >>= 1;
if (p) base = base * base % MOD;
}
return ret;
}

int main(void) {
// init
// the index is the number of answer's segments
pre[2] = 0;
pre[3] = 4;
int maxn;
for (LL i = 4; pre[i - 1] <= 1e9; i++) {
pre[i] = pre[i - 1] + i + 1;
// cout << i << " : " << pre[i] << "\n";
maxn = i;
}
// build the fractorial numbers' array
fractorial[0] = fractorial[1] = 1;
for (LL i = 2; i < SIZE; i++) {
fractorial[i] = fractorial[i - 1] * i % MOD;
}
// build the modulo reverse identity elements' array
for (LL i = 1; i < SIZE; i++) {
mr[i] = fastPow(i, MOD2);
}
int t;
LL x;
// start to deal with input
scanf("%d", &t);
while (t--) {
scanf("%lld", &x);
if (x < 5) {
printf("%lld\n", x);
continue;
}
// offset is 5
x -= 5;
int l = 2, r = maxn;
while (l < r) {
int mid = (l + r) >> 1;
if (pre[mid] > x) r = mid;
else l = mid + 1;
}
if (pre[l] > x) l--;
x += 5;
LL diff = x - (l * (l + 3) / 2);
// printf("cnt : %d\n", l);
// printf("fractorial[%d]: %lld\n", l + 2, fractorial[l + 2]);
// printf("pre[%d]: %lld\n", l, pre[l]);
// printf("diff: %lld\n", diff);
if (diff > l) {
printf("%lld\n", fractorial[l + 3] * mr[2] % MOD * mr[2 * l + 3 - diff] % MOD);
} else {
printf("%lld\n", fractorial[l + 2] * mr[l + 2 - diff] % MOD);
}
}
}```

https://www.cnblogs.com/hsd-/p/5325780.html

https://oeis.org/A034893