现在的位置: 首页 > 编程语言 > 正文

欧拉函数

2019年08月21日 编程语言 ⁄ 共 980字 ⁄ 字号 评论关闭

poj2478--裸题

题解:就是求n以内 所有互素的数 的组合数! 即n以内所有整数的欧拉函数之和!

欧拉函数知识点 可以参考白书。

//	2478	Accepted	4084K	235MS	C++	620B	
//	2478	Accepted	8000K	282MS	C++	735B	
#include <iostream>//详细可以参见 白书!
#include<cstdio>
#include<cstring>
using namespace std;
#define N 1000010
int phi[N];
void Eula()
{
    int i,j;
    memset(phi,0,sizeof(phi));//筛法 求出N以内的所有 n以内的互素数!
    for(i=2;i<=N;i++)//素数从2开始
    {
        if(!phi[i])
        {
            for(j=i;j<=N;j+=i)
            {
                if(!phi[j]) phi[j]=j;//赋给该数 素因子分解后 它的最小素因子!
                phi[j]=phi[j]/i*(i-1);//后面每一个素因子可以组成的数 都用公式刷新下该数的 欧拉数!
            }
        }
    }
    //for(i=2;i<=N;i++)phi[i]+=phi[i-1]; 第二种方法可以把所有答案打好表!
}
int main()
{
    Eula();
    int n,i;
    __int64 sum;
    while(scanf("%d",&n),n)
    {
        sum=0;
        for(i=2;i<=n;i++)
            sum+=phi[i];
        printf("%I64d\n",sum);
    }
    return 0;
}

上面是打表的方法--适用于多数据 而数据小;

以下为求单个 数的欧拉函数--适用于大数据 小规模;

#include<stdio.h>
long long phi(long long a)
{
long long temp=a;
for(long long i=2;i*i<=a;i++)
if(a%i==0)
{
while(!(a%i))a/=i;  //该数有此素因子,先除完.
temp=temp/i*(i-1);  //利用公式 n/(1-1/p);
}
if(a!=1)  //最后a不是1 就是一个素数.
temp=temp/a*(a-1);//再利用公式除一下就ok!
return temp;
} 
int main() 
{
long long a,b,c;
while(scanf("%lld",&a)!=EOF)
printf("%lld\n",phi(a));
return 0;
}

【上篇】
【下篇】

抱歉!评论已关闭.