我先来：帮Imken求调
by SqrtSecond @ 2023-06-25 21:33:53
@[SqrtSecond](/user/217233) 你差不多得了你帮不帮我
by QAQ__ @ 2023-06-25 21:38:26
@[SqrtSecond](/user/217233) 满足一个高二期末之人的临终遗愿好不好
by QAQ__ @ 2023-06-25 21:38:47
@[QAQ__](/user/627636) 抱歉我没时间（（（
我尽量帮你看看
by SqrtSecond @ 2023-06-25 21:40:24
@[Caiest_Oier](/user/932169) 线性筛都 $O(n)$ 了，瓶颈不在整除分块吧
by QAQ__ @ 2023-06-25 21:45:01
@[QAQ__](/user/627636) 事实证明，改为分块就过了
by Caiest_Oier @ 2023-06-25 21:57:14
@[QAQ__](/user/627636)
```cpp
#include <bits/stdc++.h>
using namespace std;
int phi[1000005], prime[1000005]; bool is_prime[1000005];
long long g=1;
long long qp(long long n, long long m, long long p){
long long ans=1,base=n;
while(m){
if(m&1)(ans*=base)%=p;
(base*=base)%=p;
m>>=1;
}
return ans;
}
void pre() {
for (int i = 1; i <= 1000000; i++) {
is_prime[i] = 1;
}
int cnt = 0;
is_prime[1] = 0;
phi[1] = 1;
for (int i = 2; i <= 1000000; i++) {
if (is_prime[i]) {
prime[++cnt] = i;
phi[i] = i - 1;
}
for (int j = 1; j <= cnt && i * prime[j] <= 1000000; j++){
is_prime[i * prime[j]] = 0;
if (i % prime[j])phi[i * prime[j]] = phi[i] * phi[prime[j]];
else {
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
}
}
}
int main() {
long long n; pre();
for (int i=1; i<=1000000; i++) (phi[i] += phi[i-1]) %= 104857600;
long long prod = 1;
cin>>n;
for(int i=1; i<=n; i++)(prod *= i) %= 104857601;
prod=qp(prod,2*n,104857601);
for(int i=1;i<=n;i++){
g=(g*i)%104857601;
if((n/i)!=(n/(i+1))||i==n){
(prod*=qp(qp(g,4*phi[n/i]-2,104857601),104857599,104857601))%=104857601;
g=1;
}
}
cout<<prod<<endl;
return 0;
}
```
by Caiest_Oier @ 2023-06-25 21:57:48
乘的时候不要每个都乘上去，n/i发生变化的时候再一气乘上去
by Caiest_Oier @ 2023-06-25 21:58:31
@[Caiest_Oier](/user/932169) 谢谢，贴贴 kyst（
by QAQ__ @ 2023-06-25 22:00:20