求助,还是灵异事件
查看原帖
求助,还是灵异事件
245875
Ame__楼主2020/7/17 15:48

推完柿子打出来代码之后我一直以为自己推错了,但是重新打了一次一模一样的代码发现a了???找了半天没找出来bug请求帮忙找一下 错误代码

#include<bits/stdc++.h>

#define LL long long

using namespace std;

template <typename T> void read(T & t){
	t = 0;int f = 1;char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-')f =- 1;ch = getchar();}
	do{t = t * 10 + ch - '0';ch = getchar();}while(ch >= '0' && ch <= '9');t *= f;
}

const int kato = 1e5 + 10;

bool ispri[kato];

LL prime[kato] , phi[kato] , cnt , sum[kato];

LL n , m;

inline void get_phi(){
	for(int i = 2;i <= kato;i ++){
		if(!ispri[i]){
			prime[++ cnt] = i;
			phi[i] = i - 1;
		}
		for(int j = 1;j <= cnt && (i * prime[j] <= kato);j ++){
			ispri[i * prime[j]] = 1;
			if(i % prime[j] == 0){
				phi[i * prime[j]] = phi[i] * prime[j];
				break;
			}
			phi[i * prime[j]] = phi[i] * (prime[j] - 1);
		}
	}
	for(int i = 1;i <= kato;i ++){
		//if(i<=10) cerr<<phi[i]<<"\n";
		sum[i] = sum[i - 1] + phi[i];
	}
}

int main(){
	read(n);read(m);
	phi[1] = 1;
	get_phi();
	if(n > m){
		swap(n , m);
	}
	LL ans = 0;
	for(int l = 1 , r;l <= n;l = r + 1){
		r = min(n / (n / l) , m / (m / l));
		ans += 1LL * (sum[r] - sum[l - 1]) * (n / l) * (m / l);
	}
	ans = 1LL * 2 * ans - n * m;
	printf("%lld" , ans);
    return 0;                         
}

正确代码

#include<bits/stdc++.h>

#define LL long long

using namespace std;

template <typename T> void read(T & t){
	t = 0;int f = 1;char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-')f =- 1;ch = getchar();}
	do{t = t * 10 + ch - '0';ch = getchar();}while(ch >= '0' && ch <= '9');t *= f;
}

const int kato = 1e5 + 1;

bool ispri[kato];

LL phi[kato] , sum[kato] , prime[kato] , n , m , cnt;

inline void get_phi(){
    for(int i = 2;i <= kato;i ++){
        if(!ispri[i]){
        	prime[++ cnt] = i;
			phi[i] = i - 1;
		}
        for(int j = 1;j <= cnt && (i * prime[j] <= kato);j ++){
            ispri[i * prime[j]] = 1;
            if(i % prime[j] == 0){
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
    }
    for(int i = 1;i <= kato;i ++){
    	//if(i<=10) cerr<<phi[i]<<"\n";
        sum[i] = sum[i - 1] + phi[i];
    }
}

inline int Ame_(){
    read(n);read(m);
    phi[1] = 1;
	get_phi();
    LL ans = 0;
    if(n > m){
    	swap(n , m);
    }
    for(int l = 1 , r;l <= n;l = r + 1){
        r = min(n / (n / l) , m / (m / l));
        ans += 1LL * (sum[r] - sum[l - 1]) * (n / l) * (m / l);
    }
    ans = 1LL * 2 * ans - n * m;
    printf("%lld" , ans);
    return 0;
}

int Ame__ = Ame_();

int main(){;}
2020/7/17 15:48
加载中...