推完柿子打出来代码之后我一直以为自己推错了,但是重新打了一次一模一样的代码发现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(){;}