【算法】数论---欧拉函数

什么是欧拉函数?

对于正整数n,欧拉函数是小于或等于n的正整数中与n互质的数的数目,记作φ(n)

φ(1)=1

当m,n互质时,φ(mn)=φ(m)∗φ(n)

 


一、求一个正整数的欧拉函数---(先对它分解质因数,然后套公式)

int x; cin>>x;
int ans=x;
        
map<int,int>h;
for(int i=2;i<=x/i;i++)
{
    while(x%i==0)
    {
        x/=i;
        h[i]++;
    }
}
if(x>1)h[x]++;
        
for(auto i:h)
{
    int j=i.first;  //因为j最大不超过2x10^9,所有j的数据类型用int就足够了
    ans=ans/j*(j-1);  //因为每个j都是ans的质因子,所有ans/j肯定可以整除的,并且因为ans/j*(j-1)的结果肯定会小于ans,所有ans的数据类型用int就足够了
}//这里必须得是ans/j*(j-1)这个顺序,防止爆int
        
cout<<ans<<endl;

二、求一个正整数的欧拉函数---线性筛法

#include<iostream>
using namespace std;

const int N=1000010;

int primes[N],idx=0;

bool st[N];int ou[N];

int main()
{
    int n; cin>>n;
    for(int i=2;i<=n;i++)
    {
        if(!st[i])
        {
            primes[idx++]=i;
            ou[i]=i-1;
        }

        for(int j=0;primes[j]*i<=n;j++)
        {
            st[primes[j]*i]=true;  //primes[j]*i将会遍历所有的和数,然后在这里将它们标记(筛掉),再在下面将它们的欧拉函数求出

            if(i%primes[j]==0)  //i%primes[j]==0说明primes[j]是i的最小质因数
            {
                ou[primes[j]*i]=ou[i]*primes[j];
                break;
            }
            else  //i%primes[j]!=0说明primes[j]是比i的最小质因数还要小的质数
            {
                ou[primes[j]*i]=ou[i]*primes[j]/primes[j]*(primes[j]-1);
            }
        }
    }

    ou[1]=1;

    long long ans=0;
    for(int i=1;i<=n;i++)ans+=ou[i];
    cout<<ans;

    return 0;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/282192.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

2024新年贺词:从“第一次”到“每一次”,锐意进取,未来可期

从“第一次”到“每一次”&#xff1a;锐意进取&#xff0c;未来可期&#xff01; 2023年&#xff0c;对和数来讲&#xff0c;是很不平凡的一年。在这一年里&#xff0c;我们共同创造并见证了很多个“第一次”。2023年8月&#xff0c;SHANHAI国际版正式在泰国上线。第一次“出…

LLM之RAG实战(九)| 高级RAG 03:多文档RAG体系结构

在RAG&#xff08;检索和生成&#xff09;这样的框架内管理和处理多个文档有很大的挑战。关键不仅在于提取相关内容&#xff0c;还在于选择包含用户查询所寻求的信息的适当文档。基于用户查询对齐的多粒度特性&#xff0c;需要动态选择文档&#xff0c;本文将介绍结构化层次检索…

python+opencv实现图片/短视频一键去水印

目录 0 前言1 准备工作2 读取图片或视频3 添加回调获取鼠标绘制水印区域4 调用opencv函数5 绘制蒙版主循环6 去水印主循环总结 0 前言 在制作ppt个人文章或者分享图片过程中&#xff0c;经常会遇到一些带有水印的情况&#xff0c;不少人都希望能够去除这些水印&#xff0c;提高…

分布式存储考点梳理 + 高频面试题

欢迎来到分布式存储模环节&#xff0c;本文我将和你一起梳理面试中分布式系统的数据库的高频考点&#xff0c;做到温故知新。 面试中如何考察分布式存储 广义的分布式存储根据不同的应用领域&#xff0c;划分为以下的类别&#xff1a; 分布式协同系统 分布式文件系统 分布式…

数据结构:单调栈

1.单调栈 单调栈是一种数据结构&#xff0c;其中存放的数据应该是有序的&#xff0c;所以单调栈也有单调递减栈和单调递增栈 单调递增栈&#xff1a;栈顶到栈底的元素大小是从小到大 单调递减栈&#xff1a;栈顶到栈底的元素大小是从大到小 单调栈主要就是用来求一个给定序列中…

上海周边公路骑行路线分享,维乐带你抓住秋天的小尾巴

路线一&#xff1a;松江郊里骑行      在魔都上海&#xff0c;藏着一条自然风景适宜&#xff0c;能眺望黄浦江的美丽骑行路线。导航到华长路杨家角就能到达起点&#xff0c;一路向西&#xff0c;这里路况非常好&#xff0c;只有一条小道&#xff0c;没有汽车的障碍&#xf…

数组(定义,静态初始化,地址值,元素访问,索引,遍历,动态初始化,两种初始化的区别,练习)

文章目录 1.数组概念&#xff1a; 2.数组的定义格式一&#xff1a;格式二&#xff1a;详解&#xff1a;注意点&#xff1a; 3.数组的静态初始化完整格式&#xff1a;格式详解&#xff1a;注意点&#xff1a;简化格式:练习1&#xff1a;练习2&#xff1a;练习3&#xff1a; 4.地…

使用opencv+tesseract识别图片中的表格

描述 在java环境中使用opencv和tesserac识别一个图片表格 环境&#xff1a;opencv和tesseract安装在linux环境下&#xff0c;docker将运行springboot服务 opencv和tesseract的安装和docker加载可参考之前的文章 过程 将图片进行预处理&#xff0c;过滤掉颜色等干扰元素 提…

基于Ubuntu环境Git服务器搭建及使用

基于Ubuntu环境Git服务器搭建及使用 Chapter1 搭建本地git服务器及详细操作步骤1.搭建本地git服务器1.1 环境1.2 服务端配置1.3 创建git专属用户1.4 创建git仓库1.5 配置免密登录基础 2.客户端拉取推送代码2.1客户端创建ssh公钥 2.2 免密配置3.仓库使用&#xff08;拉取及推送代…

记chrome的hackbar无法post php://input的问题

尽管hackbar支持post请求体&#xff0c;但是当请求体里面没有等于号的时候&#xff0c;无法post出去&#xff0c;这样如果需要使用php://input绕过waf的时候就没法做。 在开发人员工具的网络里面可以看到不使用等于号的情况下没有荷载。 之后在这里看到了解决方法&#xff0c;…

【javaSE】代理并不难

代理&#xff1a; 代理模式最主要的就是在不改变原来代码&#xff08;就是目标对象&#xff09;的情况下实现功能的增强 在学习AOP之前先了解代理&#xff0c;代理有两种&#xff1a;一种是动态代理&#xff0c;一类是静态代理。 静态代理 相当于是自己写了一个代理类&#…

pandas将dataframe列中的list转换为多列

在应用机器学习的过程中&#xff0c;很大一部分工作都是在做数据的处理&#xff0c;一个非常常见的场景就是将一个list序列的特征数据拆成多个单独的特征数据。 比如数据集如下所示&#xff1a; data [[John, 25, Male,[99,100,98]],[Emily, 22, Female,[97,99,98]],[Michae…

JUC Lock 锁入门

文章目录 死锁&#xff08;Deadlock&#xff09;通过 Visualvm 等工具排查死锁 活锁park & unpark与 wait & notify 的区别park & unpark 实现&#xff1a;点外卖 Lock 对象ReentrantLock 可重入锁可重入lockInterruptibly 方法上锁&#xff08;可打断&#xff09;…

门诊病历系统教程,社区诊所电子处方系统软件操作教程

一、软件程序问答 门诊病历系统教程&#xff0c;社区诊所电子处方系统软件操作教程 1、电子处方软件在开处方时候&#xff0c;可以一键导入模板吗&#xff1f; 如下图&#xff0c;软件以 佳易王诊所电子处方软件V17.1为例说明 软件右侧点击 配方模板&#xff0c;只需输入症…

以太坊代币标准解读及相关Dapp的搭建

文章目录 什么是以太坊代币标准1、什么是以太坊2、以太坊代币标准 同质化代币 Dapp 搭建1、MetaMask 的安装2、Ganache 的安装3、实现 ERC-20 代币协议4、前端页面的编写5、部署流程及操作演示 什么是以太坊代币标准 1、什么是以太坊 以太坊&#xff08;Ethereum&#xff09;是…

2024年,程序员有哪些危机,有什么应对方式?

在2024年&#xff0c;程序员可能面临的危机主要包括技术更新迅速、职业竞争激烈、工作与生活平衡困难等方面。 为了应对这些危机&#xff0c;程序员可以采取以下策略&#xff1a; 技术更新迅速&#xff1a;随着技术的不断发展&#xff0c;新的编程语言和工具不断涌现&#xff…

52.网游逆向分析与插件开发-游戏反调试功能的实现-检测调试器

码云地址&#xff08;master分支&#xff09;&#xff1a;https://gitee.com/dye_your_fingers/sro_-ex.git 码云版本号&#xff1a;be9f058bfaaa4b015f2659db842e07ee37e58996 代码下载地址&#xff0c;在 SRO_EX 目录下&#xff0c;文件名为&#xff1a;SRO_Ex检测调试器.z…

迈向通用异常检测和理解:大规模视觉语言模型(GPT-4V)率先推出

PAPERCODEhttps://arxiv.org/pdf/2311.02782.pdfhttps://github.com/caoyunkang/GPT4V-for-Generic-Anomaly-Detection 图1 GPT-4V在多模态多任务异常检测中的综合评估 在这项研究中&#xff0c;我们在多模态异常检测的背景下对GPT-4V进行了全面评估。我们考虑了四种模式&#…

c 生成16×16像素点的rgb格式图片

想验证jpeg 编解码各个环节是否正确&#xff0c;特小尺寸的yuv格式图片找不到。特意用c代码生成一个1616像素点的rgb格式图片,再转换为yuv444格式&#xff0c;再88分割&#xff0c;余弦转换&#xff0c;量化&#xff0c;Z变换&#xff0c;霍夫曼编码&#xff0c;生成比特流&…

你真的懂Hello World!吗?(编译与链接,静态链接与动态链接)

&#x1f4ab;Hello World! 对于大家来说Hello World!应该是最熟悉不过的一句话&#xff0c;我们从Hello World!走进了计算机的世界&#xff0c;但是你真的了解Hello World!吗&#xff1f;你又思考过它背后蕴含的机理吗&#xff1f;他是怎么从代码变成程序的你真的思考过吗&…