关于一个变量造成的TLE
  • 板块学术版
  • 楼主_Cyan_
  • 当前回复5
  • 已保存回复5
  • 发布时间2023/7/5 09:47
  • 上次更新2023/11/3 11:33:35
查看原帖
关于一个变量造成的TLE
480292
_Cyan_楼主2023/7/5 09:47

rt,在做P5221的时候,我推莫反时没有推完,推到一半用整除分块套整除分块来做,而在第二个整除分块中,使用了一个叫 numnum 的局部变量来存当前的下取整的值,这样在卡了下空间后过了:记录详情 。

代码:

#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;
}

但是如果我删了 numnum 这一个值,直接将 numnum 换成⌊nl⌋\lfloor \frac{n}{l} \rfloor 结果甚至 10s10s 都输不出 10610^{6} 的答案,我查了一下整除分块套整除分块的复杂度,确实是 n34n^{\frac{3}{4}} 次方,并不会炸,所以谁能告诉我这是为什么吗?

2023/7/5 09:47
加载中...