@[A·H_](/space/show?uid=31293) `inv`不用存吧
可能写法上要再优化一下
我现在30分WA，很难受。。。
估计是哪里`long long`的问题
by GKxx @ 2019-02-15 21:32:14
@[GKxx](/space/show?uid=72071) 现在TLE了一些点QwQ
by Adove @ 2019-02-15 21:50:32
@[A·H_](/space/show?uid=31293) 您至少不WA，我现在很难受。。。
您要不帮我看一下？
by GKxx @ 2019-02-15 22:00:38
@[GKxx](/space/show?uid=72071) 好啊QwQ
by Adove @ 2019-02-15 22:01:22
@[A·H_](/space/show?uid=31293)
```cpp
#include <cctype>
#include <cstdio>
#include <climits>
#include <algorithm>
#include <bitset>
template <typename T> inline void read(T& x) {
int f = 0, c = getchar(); x = 0;
while (!isdigit(c)) f |= c == '-', c = getchar();
while (isdigit(c)) x = x * 10 + c - 48, c = getchar();
if (f) x = -x;
}
template <typename T, typename... Args>
inline void read(T& x, Args&... args) {
read(x); read(args...);
}
template <typename T> void write(T x) {
if (x < 0) x = -x, putchar('-');
if (x > 9) write(x / 10);
putchar(x % 10 + 48);
}
template <typename T> inline void writeln(T x) { write(x); puts(""); }
template <typename T> inline bool chkmin(T& x, const T& y) { return y < x ? (x = y, true) : false; }
template <typename T> inline bool chkmax(T& x, const T& y) { return x < y ? (x = y, true) : false; }
typedef long long LL;
const int maxn = 1e6 + 7;
const LL mod = 104857601;
int pri[maxn / 10];
std::bitset<maxn> v;
int musum[maxn];
int n;
inline void sieve(int n) {
musum[1] = 1;
for (int i = 2; i <= n; ++i) {
if (!v.test(i)) { pri[++pri[0]] = i; musum[i] = -1; }
for (int j = 1; j <= pri[0]; ++j) {
int x = pri[j] * i;
if (x > n) break;
v.set(x);
if (!(i % pri[j])) { musum[x] = 0; break; }
else musum[x] = -musum[i];
}
}
for (int i = 2; i <= n; ++i)
musum[i] += musum[i - 1];
}
inline LL qpow(LL x, LL k) {
LL s = 1;
for (; k; x = x * x % mod, k >>= 1)
if (k & 1) s = s * x % mod;
return s;
}
inline LL solve(int n) {
LL ans = 1;
for (int d = 1; d <= n; ++d) {
LL tmp = 0;
for (int l = 1, r; l <= n / d; l = r + 1) {
r = (n / d) / (n / d / l);
tmp = (tmp + 1ll * ((musum[r] - musum[l - 1]) % mod + mod) % mod * (n / d / l) % mod * (n / d / l) % mod) % mod;
}
ans = ans * qpow(d, tmp) % mod;
}
ans = ans * ans % mod;
return qpow(ans, mod - 2);
}
int main() {
read(n);
sieve(n);
LL fac = 1;
for (int i = 1; i <= n; ++i) fac = fac * i % mod;
LL ans = qpow(fac, 2 * n) * solve(n) % mod;
writeln(ans);
return 0;
}
```
by GKxx @ 2019-02-15 22:17:28
已AC
by Adove @ 2019-02-16 07:53:09
如果你都是萌新了，那我就是……
@[A·H_](/space/show?uid=31293)
by shaocy @ 2019-04-20 20:49:46