首页 > 其他 > 详细

欧拉函数与欧拉打表解决实际问题

时间:2014-07-28 11:19:00      阅读:364      评论:0      收藏:0      [点我收藏+]

 

1.欧拉函数的定义:

   欧拉函数phi(x)等于不超过x且与x互素的整数的个数。

2.欧拉函数的求法:推导过程见随笔《欧拉函数与容斥原理》.

3.代码实现欧拉函数:

 

 1 int euler_phi(int n)
 2 {
 3     int m=(int)sqrt(n+0.5);//取一半就行,简化计算
 4     int ans=n;
 5     for(int i=2;i<=m;i++)
 6         if(n%i==0)//找素因子
 7         {
 8             ans=ans/i*(i-1);//公式的运用
 9             while(n%i==0)n/=i;//除尽
10         }
11     if(n>1)ans=ans/n*(n-1);//如果除到最后还有一个数且是大于1的素数,那么采用同样的公式再算一次
12 }

 

4.欧拉函数打表:(把一定范围内的整数的欧拉函数值存储起来

 1 int phi[maxn];
 2 void phi_table(int n)
 3 {
 4     for(int i=2;i<=n;i++)phi[i]=0;//赋初值为0
 5     phi[1]=1;
 6     for(int i=2;i<=n;i++)
 7         if(!phi[i])
 8             for(int j=i;j<=n;j+=i)
 9             {
10                 if(!phi[j])phi[j]=j;//素数一般都会赋初值为自身
11                 phi[j]=phi[j]/i*(i-1);
12             }
13 }

5解决实际问题:

POJ 2478

#include <iostream>
#include <stdio.h>
using namespace std;
#define LL long long
LL F[1000100];
int phi[1000100];

void phi_table(int n)
{
    for(int i=2;i<=n;i++)phi[i]=0;
    phi[1]=1;
    for(int i=2;i<=n;i++)
        if(!phi[i])
            for(int j=i;j<=n;j+=i)
            {
                if(!phi[j])phi[j]=j;
                phi[j]=phi[j]/i*(i-1);
            }
}

int main()
{
    int n;
    F[1]=0;
    phi_table(1000000);
    for(int i=2;i<=1000000;i++) F[i] = F[i-1]+phi[i];
    while(scanf("%d",&n)&&n!=0){
        cout<<F[n]<<endl;
    }
    return 0;
}

欧拉函数打表能快速处理问题,一般不会超时。

 

欧拉函数与欧拉打表解决实际问题,布布扣,bubuko.com

欧拉函数与欧拉打表解决实际问题

原文:http://www.cnblogs.com/khbcsu/p/3872218.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!