rt,在做P5221的时候,我推莫反时没有推完,推到一半用整除分块套整除分块来做,而在第二个整除分块中,使用了一个叫 num 的局部变量来存当前的下取整的值,这样在卡了下空间后过了:记录详情 。
代码:
#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read(){
int x=0,f=1; char c=getchar();
while(!isdigit(c)){if(c=='-') f=-1; c=getchar();}
while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48); c=getchar();}
return x*f;
}
const int mod=104857601,N=1e6+5,Mod=104857600;
short mu[N];
int pri[78499],cnt;
bool vis[N];
int jie[N];
inline void init(){
mu[1]=1;
for(int i=2;i<=N-5;i++){
if(!vis[i]) pri[++cnt]=i,mu[i]=-1;
for(int j=1;j<=cnt&&pri[j]*i<=N-5;j++){
vis[i*pri[j]]=1;
if(i%pri[j]==0) break;
mu[i*pri[j]]=-mu[i];
}
}
for(int i=1;i<=N-5;i++) mu[i]=mu[i-1]+mu[i];
jie[0]=jie[1]=1;
ll f=1;
for(int i=2;i<=N-5;i++) f=f*i%mod,jie[i]=f;
}
ll qpow(ll a,ll b){
ll res=1;
while(b){
if(b&1) res=res*a%mod;
a=a*a%mod,b>>=1;
}
return res;
}
ll val(int n){
ll res=0,num;
for(int l=1,r;l<=n;l=r+1){
r=n/(n/l);
num=n/l;//就是这个
res=(res+num*num%Mod*(mu[r]-mu[l-1]+Mod)%Mod)%Mod;
}
return res;
}
signed main(){
init();
int n=read();
ll ans=1,res=qpow(jie[n],2*n);
for(int l=1,r;l<=n;l=r+1){
r=n/(n/l);
int vv=val(n/l);
ll num=(ll)jie[r]*qpow(jie[l-1],mod-2)%mod;
ans=ans*qpow(num,vv)%mod;
}
ans=ans*ans%mod;
cout<<res*qpow(ans,mod-2)%mod;
}
但是如果我删了 num 这一个值,直接将 num 换成⌊ln⌋ 结果甚至 10s 都输不出 106 的答案,我查了一下整除分块套整除分块的复杂度,确实是 n43 次方,并不会炸,所以谁能告诉我这是为什么吗?