数论——欧拉函数

佚名 6年前 (2019-04-26) 随笔 2114人围观抢沙发百度已收录

欧拉函数：

对正整数n，欧拉函数是小于等于n的正整数中与n互质的数的数目（φ(1)=1）。

性质：

1. 欧拉函数是积性函数——若m,n互质，φ(mn)=φ(m)φ(n)
2. 当n为奇数，φ(2n)=φ(n)
3. 若n为质数，φ(n)=n-1

代码：

int euler(int n)
{
    int res=n,m=sqrt(n+0.5);
    for(int i=2;i<=m&&n!=1;++i)
    {
        if(n%i==0)
        {
            res=res/i*(i-1);
            while(n%i==0)
                n/=i;
        }
    }
    if(n!=1)
        res=res/n*(n-1);
    return res;
}

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

欧拉函数应用：

题目链接：

https://cn.vjudge.net/problem/HDU-1787

代码：

#include <cstdio>
#include <math.h>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;

const int maxn=32768;

int euler(int n)
{
    int res=n,m=sqrt(n+0.5);
    for(int i=2;i<=m&&n!=1;++i)
    {
        if(n%i==0)
        {
            res=res/i*(i-1);
            while(n%i==0)
                n/=i;
        }
    }
    if(n!=1)
        res=res/n*(n-1);
    return res;
}

int main()
{
    int n;
    while(scanf("%d",&n)&&n)
        printf("%d\n",n-1-euler(n));
    return 0;
}