欧拉函数模板

简介: 欧拉函数:表示1-(n-1)中,与n互质的数的个数 本以为学会容斥原理就不必再看欧拉函数,可是偏偏就是有些题用容斥原理解不了,必须参考欧拉,没办法只好回头看欧拉函数 下面贴一个筛法求欧拉函数模板: //初始化eu[1]=0或者eu[1]=1,具体情况根据题目变化!//下面计算2-1...

欧拉函数:表示1-(n-1)中,与n互质的数的个数

本以为学会容斥原理就不必再看欧拉函数,可是偏偏就是有些题用容斥原理解不了,必须参考欧拉,没办法只好回头看欧拉函数

下面贴一个筛法求欧拉函数模板:

//初始化eu[1]=0或者eu[1]=1,具体情况根据题目变化!
//下面计算2-10000的欧拉函数
const int MAX = 10001;
int eu[MAX];//不要忘记初始化eu[1]. 
void eular(){
    for(int i=2;i<MAx;i++){
        if(!eu[i])
            for(int j=i;j<MAX;j+=i){
                if(!eu[j]) eu[j]=j;
                eu[j]=eu[j]/i*(i-1);
            }
    }
}
目录
相关文章
|
6月前
欧拉函数及模板
欧拉函数及模板
59 1
|
6月前
|
机器学习/深度学习
分解质因子+欧拉函数
分解质因子+欧拉函数
33 0
约数个数和欧拉函数
约数个数和欧拉函数
81 0
|
6月前
|
编译器 C++
C++函数模板:函数模板与特例化解析
C++函数模板:函数模板与特例化解析
69 2
|
机器学习/深度学习 算法
欧拉函数算法的实现
欧拉函数算法的实现
欧拉函数算法的实现
|
人工智能
欧拉函数
笔记
99 0
欧拉函数
两种欧拉函数模板
欧拉函数的作用:一个数n,求小于n的互质的个数。特例:1——oula(1)=1;
82 0
两种欧拉函数模板
|
算法
数学知识:欧拉函数
复习acwing算法基础课的内容,本篇为讲解数学知识:欧拉函数,关于时间复杂度:目前博主不太会计算,先鸽了,日后一定补上。
180 0
数学知识:欧拉函数