欧拉函数和最大公约数

 分析:如果两个数的最大公约数是一个质数p,那么这两个数都除以p,得到的两个数的最大公约数一定是1.

反证法:如果得到的两个数的最大公约数不是1,那么把此时的最大公约数乘以上边的最大公约数,得到的一定比上述的最大公约数大,那么上述的最大公约数就不是最大那两个数的最大公约数,所以结论错误。即得到的两个数的最大公约数一定是1.

由于发现两个数都除以p之后,得到的数的最大公约数是1,那么我们可以想到欧拉函数,此时就可以先处理欧拉函数和欧拉函数的前缀和,然后枚举1~n的所有质数,每次求1~n/p(下取整)中与n/p(下取整)互质的个数,由于(1,2),(2,1)属于两个那么还需要乘以2,(1,1)(1,1)属于1个,最后还得减去1.

#include<bits/stdc++.h>

using namespace std;

const int N = 1e7 + 10;

int hpi[N];
int primes[N],cnt;
bool st[N];
int n;
long long s[N];

void init()
{
    hpi[1]=1;
    
    for(int i=2;i<=n;i++)
    {
        if(!st[i]) 
        {
            primes[cnt++]=i;
            hpi[i]=i-1;
        }
        
        for(int j=0;primes[j]<=n/i;j++)
        {
            st[primes[j]*i]=true;
            if(i%primes[j]==0)
            {
                hpi[primes[j]*i]=primes[j]*hpi[i];
                break;
            }
            hpi[i*primes[j]]=hpi[i]*(primes[j]-1);
        }
    }
    
    for(int i=1;i<=n;i++) s[i]=s[i-1]+hpi[i];
}
int main()
{
    cin>>n;
    
    init();
    long long res=0;
    for(int i=0;i<cnt;i++)
    {
        int p=primes[i];
        res+=(2*s[n/p]-1);
    }
    cout<<res<<endl;
    return 0;
}

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

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

相关文章

【解读Spikingjelly】使用单层全连接SNN识别MNIST

原文档&#xff1a;使用单层全连接SNN识别MNIST — spikingjelly alpha 文档 代码地址&#xff1a;完整的代码位于activation_based.examples.lif_fc_mnist.py GitHub - fangwei123456/spikingjelly: SpikingJelly is an open-source deep learning framework for Spiking Neur…

Java真实面试题,offer已到手

关于学习 在黑马程序员刚刚开始的时候学习尽头非常足&#xff0c;到后面逐渐失去了一些兴趣&#xff0c;以至于后面上课会出现走神等问题&#xff0c;但是毕业时后悔晚矣。等到开始学习项目一的时候&#xff0c;思路总会比别人慢一些&#xff0c;不看讲义写不出来代码。 建议…

Kubuesphere部署Ruoyi:持久化存储配置

按照如下教程配置NFS 先服务器&#xff1a;搭建 NFS 服务器 后客户端&#xff1a;安装 NFS Client 按照链接操作以后&#xff0c;在客户端上面把目录挂载到服务端 rootclient_banana:/# mount 172.25.110.41:/mnt/nfs_share /mnt/client_floder 客户端: mount <server-ip…

【Microsoft 支持】【数据库-MySql】当您尝试从大于 5000 的 TCP 端口连接时收到错误 WSAENOBUFS (10055)

​ 一、转载原文 When you try to connect from TCP ports greater than 5000 you receive the error ‘WSAENOBUFS (10055)’ Symptoms If you try to set up TCP connections from ports that are greater than 5000, the local computer responds with the following WSAE…

什么是微服务?

2.微服务的优缺点 优点 单一职责原则每个服务足够内聚&#xff0c;足够小&#xff0c;代码容易理解&#xff0c;这样能聚焦一个指定的业务功能或业务需求&#xff1b;开发简单&#xff0c;开发效率提高&#xff0c;一个服务可能就是专一的只干一件事&#xff1b;微服务能够被小…

CVPR 2023 | 用户可控的条件图像到视频生成方法(基于Diffusion)

注1:本文系“计算机视觉/三维重建论文速递”系列之一&#xff0c;致力于简洁清晰完整地介绍、解读计算机视觉&#xff0c;特别是三维重建领域最新的顶会/顶刊论文(包括但不限于 Nature/Science及其子刊; CVPR, ICCV, ECCV, NeurIPS, ICLR, ICML, TPAMI, IJCV 等)。 本次介绍的论…

python办公自动化有用吗?,python办公自动化能干啥

这篇文章主要介绍了python自动化办公真的有用吗 知乎&#xff0c;具有一定借鉴价值&#xff0c;需要的朋友可以参考下。希望大家阅读完这篇文章后大有收获&#xff0c;下面让小编带着大家一起了解一下。 Hello大家好&#xff0c;我是小猴紫&#xff0c;一个帅气、善良、勇敢、正…

Unity ARFoundation 配置工程 (Android)

注意&#xff1a; 1、AR Core是Google的产品&#xff0c;因为谷歌制裁华为&#xff0c;所以 有些 华为机可能不支持AR Core的软件&#xff1b; 2、手机在设置里搜索Google Play&#xff0c;看看是否已经安装上了&#xff0c;如果没有装此服务&#xff0c;去商城里搜索Google Pl…

机器人CPP编程基础-01第一个程序Hello World

很多课程先讲C/C或者一些其他编程课&#xff0c;称之为基础课程。然后到本科高年级进行机器人专业课学习&#xff0c;这样时间损失非常大&#xff0c;效率非常低。 C/单片机/嵌入式/ROS等这些编程基础可以合并到一门课中进行实现&#xff0c;这些素材已经迭代三轮以上&#xf…

脚本一键生成通用接口,一分钟实现增删改查

直接使用无需看此配置 快速生成通用接口业务配置 &#xff1a; https://blog.zysicyj.top/2023/08/14/快速生成通用接口业务配置 一、插件安装 二、脚本 关注绿色聊天软件【程序员朱永胜】回复&#xff1a;1013 下载 三、使用 拷贝到扩展目录下 修改mybatisCodehelper.vm 修改i…

说一下什么是tcp的2MSL,为什么客户端在 TIME-WAIT 状态必须等待 2MSL 的时间?

1.TCP之2MSL 1.1 MSL MSL:Maximum Segment Lifetime报文段最大生存时间&#xff0c;它是任何报文段被丢弃前在网络内的最长时间 1.2为什么存在MSL TCP报文段以IP数据报在网络内传输&#xff0c;而IP数据报则有限制其生存时间的TTL字段&#xff0c;并且TTL的限制是基于跳数 1.3…

mysql中在有数据的表中新增一个主键处理方案

需求&#xff1a;因为业务需要修改表中原来的主键为新增的字段&#xff1b; 处理方案&#xff1a; 1、先将表名修改一下&#xff1b; 2、新增一个一样的表结构&#xff0c;表名与原表名一致&#xff0c;多了一个主键&#xff08;自增&#xff09;的字段&#xff1b; 3、把原…

ubuntu中安装python

最简单方便的是 apt 使用第三方的 ppa 源&#xff0c;然后直接 apt 安装 python3.9 安装 software-properties-common 获取add-apt-repository命令&#xff1a;apt install -y software-properties-common添加第三方的 ppa 源&#xff1a;add-apt-repository ppa:deadsnakes/p…

【一场专属于开发者的盛会!】------NPCon2023 AI模型技术与应用峰会(北京站)

2023年8月12日&#xff0c;由CSDN官方举办的2023年-NPCon2023 AI模型技术与应用峰会(北京站)在北京格兰云天大酒店荣重召开&#xff01; 话不多说&#xff01;上图~~~ 目录 【会议展望】 【大咖宣讲】 【CSDN活动介绍】 【开谈环节&#xff0c;我有句话说】 【现场人气】…

简单入门seleniumUI自动化测试

目录 一、selenium的介绍 二、selenium的原理 三、selenium的八种元素定位的方法 1、ID定位&#xff1a; 2 、name定位&#xff1a; 3、class定位&#xff1a; 4、tag定位&#xff1a; 5、link_text定位&#xff1a; 6、partial_link_text定位&#xff1a; 7、css定位…

【UniApp开发小程序】小程序首页(展示商品、商品搜索、商品分类搜索)【后端基于若依管理系统开发】

文章目录 界面效果界面实现工具js页面首页让文字只显示两行路由跳转传递对象将商品分为两列显示使用中划线划掉原价 后端商品controllerservicemappersql 界面效果 【说明】 界面中商品的图片来源于闲鱼&#xff0c;若侵权请联系删除关于商品分类页面的实现&#xff0c;请在我…

基于 ObjectOutputStream 实现 对象与二进制数据 的序列化和反序列化

目录 为什么要进行序列化呢&#xff1f; 如何实现 对象与二进制数据 的序列化和反序列化&#xff1f; 为什么要进行序列化呢&#xff1f; 主要是为了把一个对象&#xff08;结构化的数据&#xff09;转化成一个 字符串 / 字节数组&#xff0c;方便我们存储&#xff08;有时候需…

AWS——03篇(AWS之Amazon S3(云中可扩展存储)-01入门)

AWS——03篇&#xff08;AWS之Amazon S3&#xff08;云中可扩展存储&#xff09;-01入门&#xff09; 1. 前言2. 关于 Amazon S32.1 介绍2.1.1 简述2.1.2 详细介绍 2.2 Amazon S3 好处和功能2.3 3. 创建S3存储桶3.1 创建存储桶3.2 修改访问权限 4. 简单实用4.1 上传图片文件4.2…

海量数据迁移,亚马逊云科技云数据库服务为大库治理提供新思路

1.背景 目前&#xff0c;文档型数据库由于灵活的schema和接近关系型数据库的访问特点&#xff0c;被广泛应用&#xff0c;尤其是游戏、互联网金融等行业的客户使用MongoDB构建了大量应用程序&#xff0c;比如游戏客户用来处理玩家的属性信息&#xff1b;又如股票APP用来存储与时…

SpringBoot复习:(44)MyBatisAutoConfiguration

可以看到MyBatisAutoConfiguration引入了MyBatisProperties这个属性&#xff1a; MyBatisAutoConfiguration中配置了一个SqlSessionFactoryBean,代码如下&#xff1a; 可以配置mybatis-config.xml,需要配置文件里指定&#xff1a; mybatis.config-locationclasspath:/mybat…