#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+10;
int primes[N],cnt;
int euler[N];
bool state[N];
void get_euler(int n)
{
euler[1]=1;
for(int i=2;i<=n;i++)
{
if(!state[i])
{
primes[cnt++]=i;
euler[i]=i-1;
}
for(int j=0;primes[j]<=n/i;j++)
{
int t=primes[j]*i;
state[t]=true;
if(i%primes[j]==0)
{
euler[t]=euler[i]*primes[j];
break;
}
euler[t]=euler[i]*(primes[j]-1);
}
}
}
int main()
{
int n;
scanf("%d",&n);
get_euler(n);
LL ans=0;
for(int i=1;i<=n;i++) ans+=euler[i];
printf("%lld\n",ans);
return 0;
}1.属于是先手推数学式子，然后代码比较简单的题目
2. 线性筛法，之前接触过一道类似的线性筛法的题目：线性筛法
3.线性筛法是一个算法模板
#include<bits/stdc++.h>
using namespace std;
const int N=1e6+10;
bool state[N];
int primes[N],cnt;
void euler(int n)
{
for(int i=2;i<=n;i++)
{
if(!state[i])
{
primes[cnt++]=i;
}
for(int j=0;primes[j]<=n/i;j++)
{
int t=primes[j]*i;
state[t]=true;
if(i%primes[j]==0) break;
}
}
}
int main()
{
int n;
scanf("%d",&n);
euler(n);
printf("%d\n",cnt);
return 0;
}顺便写一下这一道题目的笔记：AcWing 868. 筛质数
4. 下面详细分析一下线性筛法之外的数学部分的内容
5.从1一直到某一个质因子的欧拉函数的数值是质因子-1，这是第一种情况
6.第二种情况，primes[j]是i的一个质因子，根据欧拉函数公式，
euler[i]=i*(1-1/p1)*(1-1/p2)*...*(1-1/pk);
euler[i*primes[j]]=(i*primes[j])*(1-1/p1)*(1-1/p2)*...*(1-1/pk);
因为primes[j]是某一个质因子，所以后面部分是一样的，上面下面相互对照，可以得到，
euler[t]=euler[i]*primes[j];7.第三种情况，primes[j]不是i的质因子，
euler[i]=i*(1-1/p1)*(1-1/p2)*...(1-1/pk);
euler[i*primes[j]]=(i*primes[j])*(1-1/p1)*(1-1/p2)*..*(1-1/primes[j]);
euler[i*primes[j]]=i*(1-1/p2)*...(1-1/pk)*(primes[j]-1);
//把第二行式子最后面的括号通分，和最前面的primes[j]约掉，得到第三行的式子
//再把第一行的式子和第三行的式子进行对照可以得到
euler[t]=euler[i]*(primes[j]-1);（自己可以推导出来的数学式子也很有趣呢（））
8.break是直接跳出循环，不只是跳出if的条件判断
9.以上就是这个题目的全部内容，没有比当傻瓜更简单的事儿了，为了一件事情疯狂，总有一天可以从中找到答案。
文章来源地址https://www.toymoban.com/news/detail-718275.html
文章来源：https://www.toymoban.com/news/detail-718275.html
到了这里，关于欧拉函数和线性筛法：AcWing 874. 筛法求欧拉函数的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
