@[梨衣](/user/278605) 请问对于哪些题赋值了不能输出正确结果？
by 素质玩家孙1超 @ 2020-11-19 08:57:35
定义就是phi[1]=1。
要用上phi[1]的题就错了，不用phi[1]的就没错
by 日居月诸 @ 2020-11-19 08:59:21
@[梨衣](/user/278605) 这题也要赋值吧，我赋值才过的/kk
by vеctorwyx @ 2020-11-19 08:59:32
但 $\varphi(1)$ 确实 $=1$ 啊
by Binary_Search_Tree @ 2020-11-19 09:00:03
定义里 phi 1 就是 1 吧
by sanaka87 @ 2020-11-19 09:03:28
@[素质玩家孙1超](/user/220857)
```cpp
#include<cstdio>
#define ll long long
#define maxn 10000010
using namespace std;
bool v[maxn];
ll prime[maxn],phi[maxn],tot;
void euler(ll x){
//phi[1]=1;
for(int i=2;i<=x;i++){
if(!v[i]){
prime[++tot]=i;
phi[i]=i-1;
}
for(int j=1;j<=tot&&prime[j]*i<=x;j++){
v[prime[j]*i]=1;
if(i%prime[j])
phi[i*prime[j]]=phi[i]*phi[prime[j]];
else {
phi[i*prime[j]]=phi[i]*(phi[prime[j]]+1);
break;
}
}
}
}
int main(){
ll n,ans=0;
scanf("%lld",&n);
euler(n);
//printf("%lld",phi[1]);
for(int i=1;i<=n;i++)
phi[i]+=phi[i-1];
for(int i=1;i<=tot;i++)
ans+=phi[n/prime[i]]*2;
printf("%lld",ans+tot);
}
```
本题赋值后输入 $4$ 输出变成了 $8$
by 梨衣 @ 2020-11-19 09:04:00
@[Noziro](/user/77426) 定义确实是这样但是赋值后答案就错了
by 梨衣 @ 2020-11-19 09:04:30
@[梨衣](/user/278605) 好像欧拉筛写锅了
by vеctorwyx @ 2020-11-19 09:07:56
改成这样就对了
```
if(i%prime[j])
phi[i*prime[j]]=phi[i]*phi[prime[j]];
else {
phi[i*prime[j]]=phi[i]*prime[j];
break;
```
by vеctorwyx @ 2020-11-19 09:09:14
@[vеctorwyx](/user/169422) 对于质数 $p$ 欧拉函数的值不是 $p - 1$ 吗
by 梨衣 @ 2020-11-19 09:12:12