```cpp
ans = ans * quick_pow(fac[j] * quick_pow(fac[i - 1], mod - 2, mod) % mod, ((get_euler_sum(tn, mod - 1) * 2 - 1) % (mod - 1) + (mod - 1)) % (mod - 1), mod) % mod;
```
fac 数组小了
by andyli @ 2020-06-14 13:30:19
谢谢各位巨佬！我终于 AC 了！
代码：
```cpp
#include <iostream>
#include <map>
using namespace std;
typedef long long ll;
const int N = 1e4 + 7, M = 1e6 + 7, mod = 104857601;
int prime[N], phi[N], sum[N], fac[M]; // 万恶的空间限制迫使我用 int
bool p[N];
map<ll, ll> mp;
inline ll quick_pow(ll x, ll p, ll mod){
ll ans = 1;
while (p){
if (p & 1) ans = ans * x % mod;
x = x * x % mod;
p >>= 1;
}
return ans;
}
inline void init(int n){
int cnt = 0;
p[0] = p[1] = true;
phi[1] = 1;
for (register int i = 2; i < N; i++){
if (!p[i]){
prime[++cnt] = i;
phi[i] = i - 1;
}
for (register int j = 1; j <= cnt && i * prime[j] < N; j++){
int t = i * prime[j];
p[t] = true;
if (i % prime[j] == 0){
phi[t] = phi[i] * prime[j];
break;
}
phi[t] = phi[i] * (prime[j] - 1);
}
}
for (register int i = 1; i < N; i++){
sum[i] = (sum[i - 1] + phi[i]) % (mod - 1);
}
fac[0] = fac[1] = 1;
for (register int i = 2; i <= n; i++){
fac[i] = (ll)fac[i - 1] * i % mod;
}
}
inline ll get_euler_sum(int n, int mod){
if (n < N) return sum[n];
if (mp.count(n)) return mp[n];
ll ans = (ll)n * (n + 1) / 2 % mod;
for (register int i = 2, j; i <= n; i = j + 1){
int tn = n / i;
j = n / tn;
ans = ((ans - get_euler_sum(tn, mod) * (j - i + 1) % mod) % mod + mod) % mod;
}
return mp[n] = ans;
}
int main(){
int n;
ll ans = 1;
cin >> n;
init(n);
for (register int i = 1, j; i <= n; i = j + 1){
int tn = n / i;
j = n / tn;
ans = ans * quick_pow(fac[j] * quick_pow(fac[i - 1], mod - 2, mod) % mod, ((get_euler_sum(tn, mod - 1) * 2 - 1) % (mod - 1) + (mod - 1)) % (mod - 1), mod) % mod;
}
cout << quick_pow(fac[n], n * 2, mod) * quick_pow(ans * ans % mod, mod - 2, mod) % mod;
return 0;
}
```
by Leasier @ 2020-06-14 15:57:03