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