神秘代码厌氧
查看原帖
神秘代码厌氧
755847
SJS_z楼主2025/7/30 19:20

rt

for (int i=1;i<=N;i++){
    smu[i]=smu[i-1]+mu[i];
}
for (int i=1;i<=N;i++){
	int l=1,r=0;
	for (;l<=i;l=r+1){
		r=i/(i/l);
		f[i]+=1ll*i/l*(r-l+1);
	}
}

如上代码洛谷开O2后WA0,将此处1~3行代码调整后开O2能够AC,调整后代码如下

for (int i=1;i<=N;i++){
	int l=1,r=0;
	for (;l<=i;l=r+1){
		r=i/(i/l);
		f[i]+=1ll*i/l*(r-l+1);
	}
}
for (int i=1;i<=N;i++){
	smu[i]=smu[i-1]+mu[i];
}

更为迷惑的是,下载样例1后本地开O2,即添加如下语句后样例输出正确,但洛谷样例评测显示“Wrong Answer.wrong answer On line 1 column 1, read -, expected 1.”

#pragma GCC optimize("O2")

望有dalao能帮忙解释一下可能的原因

完整厌氧代码如下:

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=5e4,S=5e4+5;
vector<int> prime;
int mu[S],smu[S];
long long f[N];
bool is_prime[S];
void init(){
	mu[1]=1;
	for (int i=2;i<=N;i++){
		if (!is_prime[i]){
			mu[i]=-1;
			prime.push_back(i);
		}
		for (int j=0;j<prime.size() && i*prime[j]<=N;j++){
			is_prime[i*prime[j]]=1;
			if (i%prime[j]==0){
				break;
			}else{
				mu[i*prime[j]]=-mu[i];
			}
		}
	}
	for (int i=1;i<=N;i++){
		smu[i]=smu[i-1]+mu[i];
	}
	for (int i=1;i<=N;i++){
		int l=1,r=0;
		for (;l<=i;l=r+1){
			r=i/(i/l);
			f[i]+=1ll*i/l*(r-l+1);
		}
	}
}
signed main(){
//	freopen("P3327_1.in","r",stdin);
//	freopen("P3327_1.myans","w",stdout);
	int T;
	cin>>T;
	init();
	while (T--){
		int n,m;
		cin>>n>>m;
		if (n>m){
			swap(n,m);
		}
		int l=1,r=0;
		long long sum=0;
		for (;l<=n;l=r+1){
			r=min(n/(n/l),m/(m/l));
			sum+=(smu[r]-smu[l-1])*f[n/l]*f[m/l];
		}
		cout<<sum<<'\n';
	}
	return 0;
} 
2025/7/30 19:20
加载中...