数论 欧拉函数_数论欧拉函数

数论 欧拉函数_数论欧拉函数欧拉函数:就是对于一个正整数n,小于n且和n互质的正整数(包括1)的个数,记作φ(n)。欧拉函数的通式:φ(n)=n*(1-1/p1)(1-1/p2)(1-1/p3)*(1-1/p4)……(1-1/pn)其中p1,p2……pn为n的所有质因数,n是不为0的整数。φ(1)=1(唯一和1互质的数就是1本身)。所以,根据通式我们可以打出以下代码:lleular(lln){…

大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元 售后保障 童叟无欺

欧拉函数:

就是对于一个正整数n,小于n且和n互质的正整数(包括1)的个数,记作φ(n) 。

欧拉函数的通式:φ(n)=n*(1-1/p1)(1-1/p2)(1-1/p3)*(1-1/p4)……(1-1/pn)

其中p1, p2……pn为n的所有质因数,n是不为0的整数。φ(1)=1(唯一和1互质的数就是1本身)。
在这里插入图片描述

所以,根据通式我们可以打出以下代码:

ll eular(ll n)
{ 
   
    ll ans = n;
    for(int i=2; i*i <= n; ++i)
    { 
   
        if(n%i == 0)
        { 
   
            ans = ans/i*(i-1);
            while(n%i == 0)
                n/=i;
        }
    }
    if(n > 1) ans = ans/n*(n-1);
    return ans;
}

其中,if(n>1)ans-=ans/n; 这个语句是为了保证我们已经除完了n的所有的素因子,有可能还会出现一个我们未除的因子,如果结尾出现n>1 ,说明我们还剩一个素因子木有除。

打表求欧拉函数:

听说这样比较快。。。。

void euler()  
{ 
     
    for(int i=2;i<maxn;i++){ 
     
        if(!E[i])  
        for(int j=i;j<maxn;j+=i){ 
     
            if(!E[j])E[j]=j;  
            E[j]=E[j]/i*(i-1);  
        }  
    }  
}
当然,还有百度百科版的:( 欧拉筛素数同时求欧拉函数)

在这里插入图片描述

void get_phi()  
{ 
     
    int i, j, k;  
    k = 0;  
    for(i = 2; i < maxn; i++)  
    { 
     
        if(is_prime[i] == false)  
        { 
     
            prime[k++] = i;  
            phi[i] = i-1;  
        }  
        for(j = 0; j<k && i*prime[j]<maxn; j++)  
        { 
     
            is_prime[ i*prime[j] ] = true;  
            if(i%prime[j] == 0)  
            { 
     
                phi[ i*prime[j] ] = phi[i] * prime[j];  
                break;  
            }  
            else  
            { 
     
                phi[ i*prime[j] ] = phi[i] * (prime[j]-1);  
            }  
        }  
    }  
}  

欧拉函数的一些性质:
① 当m,n互质时,有phi(m*n)= phi(m)*phi(n);

② 若i%p==0,有phi(i*p) = p * phi(i);

③ 对于互质x与p,有x^phi§≡1(mod p),因此x的逆元为x^(phi§-1),即欧拉定理。
(特别地,当p为质数时,phi(p)=p-1,此时逆元为x^(p-2),即费马小定理)

④ 当n为奇数时,phi(2n)=phi(n)

⑤ 若x与p互质,则p-x也与p互质,因此小于p且与p互质的数之和为phi(x)*x/2;

⑥N>1,不大于N且和N互素的所有正整数的和是 1/2 *N *eular(N)。

⑦若(N%a == 0 && (N/a)%a==0) 则有:E(N)=E(N/a)*a;

⑧若(N%a==0 && (N/a)%a!=0) 则有:E(N)=E(N/a)*(a-1);

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

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

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

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

(0)
blank

相关推荐

  • 《Android应用开发揭秘》连载2

    《Android应用开发揭秘》连载2《Android应用开发揭秘》  书名:Android应用开发揭秘作者:杨丰盛出版社:机械工业出版社ISBN:9787111291954出版日期:2010年3月(1版2次)开本:16页码:515版次:1-2定价:69元豆瓣网讨论地址:http://www.douban.com/subject/4200822/China-pub预订地址:http://www.china-pub.

  • 用python浪漫告白_python动态心形代码

    用python浪漫告白_python动态心形代码Python是一种面向他人进行的说明型编程方法,其源代码与说明器CPython遵守GPL协议,语法简洁清晰。那么,我们用少量的Python代码能做哪些有趣的东西?让小编告诉你。一、编写浪漫的心型1、图形都是由一系列的点(X,Y)构成的曲线,由于X,Y满足一定的关系,所以我们就可以建立模型,建立表达式expression,当关系满足时,两个for循环(forXinrange;forYin…

  • 【Android】Broadcasts详解

    【Android】Broadcasts详解Android应用程序可以发送广播,也可以接收Android系统或者其它应用发出的广播,这跟发布-订阅设计模式很相似。当一些受到关心的事件发生后,广播会被自动发送。举例来说,当一些系统事件(如开机,设备开始充电等)发生,Android系统会发送广播。应用程序也可以发送自定义的广播,比如当某个应用关注的事件(如数据更新等)发生后可以发送广播提醒它。系统广播当一系列系统事件发生的时候,系统会自动发送广播

  • window 下 win10 jdk8安装与环境变量的配置(超级详细)[通俗易懂]

    window 下 win10 jdk8安装与环境变量的配置(超级详细)[通俗易懂]1、jdk的下载1.1官网下载地址https://www.oracle.com/java/technologies/javase-downloads.html这里以为下载需要登录所以我准备了百度网盘1.2百度网盘下载链接:https://pan.baidu.com/s/1uBm0XqBtbdafWgn_YUSWLA提取码:2mqh2、新建文件夹2.1、新建Java文件夹我这里选择的是安装的文件夹我在H盘里面新建了个java文件夹,这里盘符可以改的CDE啥都无所谓

  • 网络端口的作用及分类[通俗易懂]

    网络端口的作用及分类[通俗易懂]1.什么是网络端口?2.网络的端口的范围及其作用3.常见网络端口列举

  • iptable详解

    一:前言防火墙,其实说白了讲,就是用于实现Linux下访问控制的功能的,它分为硬件的或者软件的防火墙两种。无论是在哪个网络中,防火墙工作的地方一定是在网络的边缘。而我们的任务就是需要去定义到底防火墙如何工作,这就是防火墙的策略,规则,以达到让它对出入网络的IP、数据进行检测。目前市面上比较常见的有3、4层的防火墙,叫网络层的防火墙,还有7层的防火墙,其实是代理层的网关。对于TCP/IP的七层模型来讲

发表回复

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

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