首页 > 代码库 > 欧拉函数模板
欧拉函数模板
1 筛选法欧拉函数 2 int euler[3000001]; 3 void getEuler() 4 { 5 memset(euler,0,sizeof(euler)); 6 euler[1] = 1; 7 for(int i = 2; i <= 3000000; i++) 8 if(!euler[i]) 9 for(int j = i; j <= 3000000; j += i)10 {11 if(!euler[j])12 euler[j] = j;13 euler[j] = euler[j]/i*(i-1);14 }15 }
求单个数的欧拉函数
long long eular(long long n)
{
long long ans = n;
for(int i = 2;i*i <= n;i++)
{
if(n % i == 0)
{
ans -= ans/i;
while(n % i == 0)
n /= i;
}
}
if(n > 1)ans -= ans/n;
return ans;
}
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。