数论——欧拉函数

数论——欧拉函数定义小于n的正整数中与n互质的数的数目(φ(1)=1)通式证明:设p是N的质因子,1~N中p的倍数有p,2p,3p,…,(N/p)*p,共N/p个。同理,若q也是N的质因子,则1~N中q的倍

大家好,又见面了,我是你们的朋友全栈君。

定义

小于n的正整数中与n互质的数的数目(φ(1)=1)

通式

<span role="heading" aria-level="2">数论——欧拉函数

证明:

  设p是N的质因子,1~N中p的倍数有p,2p,3p,…,(N/p)*p,共N/p个。

  同理,若q也是N的质因子,则1~N中q的倍数有N/q个。

  根据容斥原理,1~N中除去q的倍数与p的倍数后,数的个数为N – N/p – N/q + N/(pq) = N(1 – 1/p)(1 – 1/q)。

  而要求1~N中与N互质的数的个数,只需将N的所有质因子的倍数全部除去即可。

  利用容斥原理,因式分解后即可得到上式。

性质

(以下只列举我们需要用到的一些性质)

我们用phi(N)表示欧拉函数。

  • 当N为质数时,显然phi(N)=N-1。
  • 2.根据算数基本定理,N=p1C1*p2C2*…*pkCk 。设N的最小质因子为p,当p的指数为1时,phi(N)=(p-1)*phi(N/p)。
  • 3. 当p的指数不为1时,同2可证得phi(N)=p*phi(N/p)。

2的证明:

  根据欧拉函数通式,

  phi(N)=N*(p1-1)/p1*(p2-1)/p2*…*(pk-1)/pk,

  phi(N/p1)=N/p1*(p2-1)/p2*…*(pk-1)/pk,

  其中p1即为N的最小质因子,比较两式即可得证。

直接法

模板题链接:欧拉函数

代码实现:

int Euler(int x)
{
    int res=x;for(int i=2;i<=x/i;i++)
    {
        if(x%i==0)
        {
            res=res/i*(i-1);
            while(x%i==0)x/=i;
        }
    }
    if(x>1)res=res/x*(x-1);

    return res;
}

线性筛法

根据前面的欧拉线性筛质数的算法(可参考本人博客:数论——质数筛法),由于它在筛选的同时也求出了每个数的最小质因子,故而在其基础上求出欧拉函数即可。

模板题链接:筛法求欧拉函数

代码如下:

typedef long long ll;
const int N = 1000010;

int n;
int prime[N],cnt,v[N];
int phi[N];

ll Euler_prime(int n)
{
    phi[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!v[i])
        {
            prime[++cnt]=i;
            phi[i]=i-1;
        }
        for(int j=1;prime[j]<=n/i;j++)
        {
            int p=prime[j];
            v[p*i]=1;
            if(i%prime[j]==0)
            {
                phi[i*p]=p*phi[i];
                break;
            }
            phi[i*p]=(p-1)*phi[i];
        }
    }
    ll res=0;
    for(int i=1;i<=n;i++)res+=phi[i];
    return res;
}

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/155353.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)
blank

相关推荐

  • IntelliJ IDEA 快捷键整合(大全)

    IntelliJ IDEA 快捷键整合(大全)IntelliJIDEA快捷键整合大全1.代码标签输入完成后,按Tab,生成代码。2.查询快捷键3.其他快捷键4.svn快捷键5.调试快捷键6.重构7.其他1.代码标签输入完成后,按Tab,生成代码。Ctrl+Alt+O优化导入的类和包Alt+Insert生成代码(如get,set方法,构造函数等)或者右键(Generate)fori/sout/psvm+TabCtrl…

  • IDEA搭建Android开发环境[通俗易懂]

    IDEA搭建Android开发环境[通俗易懂]开发环境IDEA2019.3+SDK+JDK1.8。关于JDK的安装参考:JDK安装以及环境变量的配置,这里就不再说了。直接从SDK的安装开始。一、SDK的下载官方下载地址:sdk下载。不过服务器可能进不去。因为不用AndroidStudio,所以拉到最下面,选择sdk-tools就行下载完成后,解压到一个目录下即可。二、IDEA配置SDK打开Configure->Str…

  • vue转json串_vue中怎么声明一个数组

    vue转json串_vue中怎么声明一个数组一些常用更多方法介绍文章目录前言一、vue对象转数组?二、JSON数据转换1、JSON.parse2、JSON.stringify2.1、JSON.stringify高级使用总结前言提示:这里可以添加本文要记录的大概内容:例如:随着人工智能的不断发展,机器学习这门技术也越来越重要,很多人都开启了学习机器学习,本文就介绍了机器学习的基础内容。提示:以下是本篇文章正文内容,下面案例可供参考一、vue对象转数组?示例:工作中我们经常会因为和接口收到数据类型不一致,这个时候需要我们自己手动转换.

  • 一款强大的网站在线客服聊天系统:whisper搭建教程

    一款强大的网站在线客服聊天系统:whisper搭建教程简介whisper是一个在线客服系统源码,采用thinkphp5+Gatewayworker编写,性能强悍。自己搭建,控制在自己,也无需为您的数据安全担心,您可以应用在任何的正规的网站,只需要添加一段简单的js代码,就可以使您的网站拥有在线客服功能。官方网站:http://whisper.baiyf.com/截图功能支持客服分组,多客服服务,让您的服务更有条理。 支持客服…

  • BZOJ1915[USACO 2010 Open Gold 1.Cow Hopscotch]——DP+斜率优化

    BZOJ1915[USACO 2010 Open Gold 1.Cow Hopscotch]——DP+斜率优化

  • C#下使用XmlDocument详解

    C#下使用XmlDocument详解XML在开发中作为文件存储格式、数据交换的协议用的非常普遍,各个编程语言有都支持。W3C也制定了XMLDOM的标准。在这里主要介绍下.Net中的XmlDocument,包括xml读取和写入等功能。一、Xml的加载读取1、数据等准备Xml测试数据:-读取的数据,我们定义了一个实体类LocationCamera,用来保存Xml解析后的数据:public

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号