HDU - 2588 GCD

题目大意:两个正整数 a 和 b 的最大公约数 GCD(a,b),有时写成 (a,b),是 a 和 b 的最大公约数,例如,(1,2)=1,(12,18)=6。
(a,b) 可以很容易地通过欧几里得算法找到。现在 Carp 正在考虑一个更困难的问题:
给定整数 N 和 M,有多少个整数 X 满足 1<=X<=N 和 (X,N)>=M。

思路:假设(X,N)= y,那么(X / y,N / y)= 1 。因为 X <= N,所以 X / y <= N / y ,所以这道题目就变成了求 N / y 的欧拉函数之和。

代码如下:

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define endl '\n'
int euler(int n){int ret=n;for(int i=2;i*i<=n;i++){if(n%i==0){ret-=ret/i;while(n%i==0) n/=i;}}if(n>1) ret-=ret/n;return ret;
}
signed main(){IOSint _;cin >> _;while(_--){int n,m,ans=0;cin >> n >> m;for(int i=1;i*i<=n;i++){if(n%i==0){if(i>=m) ans+=euler(n/i);if(n/i>=m && i*i!=n) ans+=euler(i);}}cout << ans << endl;}return 0;
}

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【笔记】大模型长度外推技术 NTK-Aware Scaled RoPE

NTK-Aware Scaled RoPE 正弦编码(Sinusoidal)旋转位置编码RoPE编码步骤&#xff1a;旋转位置编码的优势 NTK-Aware Scaled RoPE直接外推线性内插进制转换高频外推、低频内插的理解位置编码 总结参考&#xff1a; 长度外推技术是自然语言处理&#xff08;NLP&#xff09;领域中&…

java中的二叉树

二叉树 树型结构概念相关概念树的表示形式树的应用 二叉树概念两种特殊的二叉树二叉树的性质二叉树的存储二叉树的基本操作前置说明二叉树的遍历二叉树的基本操作 二叉树相关OJ题 树型结构 概念 树是一种非线性的的数据结构&#xff0c;它是由n(n>0)个有限结点组成一个具有…

防静电监控系统为汽车电子工厂打造安全生产环境

汽车电子产品对静电极其敏感&#xff0c;微小的静电放电 (ESD) 都会导致元器件损坏&#xff0c;造成巨大的经济损失和产品质量问题。因此&#xff0c;在汽车电子工厂构建完善的ESD防静电防护体系至关重要。传统的防静电措施主要依赖人工巡检&#xff0c;效率低且难以保证实时监…

如何挑选项目管理软件?8款免费工具推荐

本文提及的8款免费优质项目管理软件有: 1.PingCode&#xff1b; 2.Worktile&#xff1b; 3.钉钉&#xff08;Dingtalk&#xff09;&#xff1b; 4.金蝶项目管理&#xff1b; 5.ProcessOn&#xff1b; 6.简道云&#xff1b; 7.Jira&#xff1b; 8.Basecamp。 在如今快速发展的商…

51单片机 复位电路

上电复位 上电复位是为了程序执行到后面&#xff0c;突然关机&#xff0c;能够让电路能够回到初始状况 使用阻容(通交流隔直流)电路完成复位 电容上电有一个过程&#xff0c;充满电所需世界大于两个机器周期 电容电充满之后&#xff0c;电压拉为0v, 整个电路就复位了 如果电压一…

面向对象(下)

7.继承 继承的基础语法 学习目标&#xff1a;理解继承的概念&#xff0c;掌握继承的使用方式&#xff0c;掌握pass关键字的作用 就是把老的设计图继承下来&#xff0c;然后修修改改成为新的设计图 我们可以使用继承&#xff0c;来完成此需求。 单继承 从头写一个新的类&…

利用Django实现MySQL数据库的内容在网页的增删改写

利用Django实现MySQL数据库的内容在网页的增删改写 1.建立项目2.定义模型3.创建视图4.创建模板5.创建表单和配置url6.最后修改7.效果 1.建立项目 输入命令django-admin startproject aaa 新建项目&#xff0c;项目名称命名为aaa&#xff0c;打开aaa文件夹&#xff0c;命令提示…

Puppeteer 与浏览器版本兼容性:自动化测试的最佳实践

Puppeteer 支持的浏览器版本映射&#xff1a;从 v20.0.0 到 v23.6.0 自 Puppeteer v20.0.0 起&#xff0c;这个强大的自动化库开始支持与 Chrome 浏览器的无头模式和有头模式共享相同代码路径&#xff0c;为自动化测试带来了更多便利。从 v23.0.0 开始&#xff0c;Puppeteer 进…

大白话讲解分布式事务-SEATA事务四种模式(内含demo)

因为这里主要是讲解分布式事务&#xff0c;关于什么是事务&#xff0c;以及事务的特性&#xff0c;单个事务的使用方式&#xff0c;以及在Spring框架下&#xff0c;事务的传播方式&#xff0c;这里就不再赘述了。但是我这里要补充一点就是&#xff0c;一提到事务大家脑子里第一…

【LLM论文日更 | 一种引入上下文的文档嵌入方法 】

论文&#xff1a;​​​​​​​https://arxiv.org/pdf/2410.02525代码&#xff1a;暂未开源机构&#xff1a;康奈尔大学领域&#xff1a;embedding model发表&#xff1a;arxiv 研究背景 研究问题&#xff1a;这篇文章要解决的问题是如何改进文档嵌入&#xff0c;使其在特定上…

短短一年多,ChatGPT 发展到什么程序了?

短短一年多&#xff0c;ChatGPT 就与 Google、Youtube、X.com等大佬级网站比肩。成为全球访问量最大的网站之一 爆发期&#xff0c;访问量月增长率高达3000%左右。网站流量从1800万次访问激增至6.72亿次只花了60来天。 2023年一项AI产品访问量统计结果中ChatGPT占比60%&#xf…

信号反射与振铃

反射来源于阻抗不匹配&#xff0c;振铃就是多次反射 对于反射要记住传输系数与反射系数 传输系数与反射系数 振铃现象计算说明

Python轴承故障诊断 (15)基于CNN-Transformer的一维故障信号识别模型

往期精彩内容&#xff1a; Python-凯斯西储大学&#xff08;CWRU&#xff09;轴承数据解读与分类处理 Pytorch-LSTM轴承故障一维信号分类(一)-CSDN博客 Pytorch-CNN轴承故障一维信号分类(二)-CSDN博客 Pytorch-Transformer轴承故障一维信号分类(三)-CSDN博客 三十多个开源…

Spark原理

主要包括&#xff1a; 核心组件的运行机制&#xff08;Master&#xff0c;Worker&#xff0c;SparkContext等&#xff09;任务调度的原理Shuffile的原理内存管理数据倾斜处理Spark优化 核心组件的运行机制 Spark 执行任务的原理&#xff1a; Spark on Yarn: Cluster模型&am…

【数据结构-邻项消除】力扣1003. 检查替换后的词是否有效

给你一个字符串 s &#xff0c;请你判断它是否 有效 。 字符串 s 有效 需要满足&#xff1a;假设开始有一个空字符串 t “” &#xff0c;你可以执行 任意次 下述操作将 t 转换为 s &#xff1a; 将字符串 “abc” 插入到 t 中的任意位置。形式上&#xff0c;t 变为 tleft “…

GPT-4o 和 GPT-4 Turbo 模型之间的对比

GPT-4o 和 GPT-4 Turbo 之间的对比 备注 要弄 AI &#xff0c;不同模型之间的对比就比较重要。 GPT-4o 是 GPT-4 Turbo 的升级版本&#xff0c;能够提供比 GPT-4 Turbo 更多的内容和信息&#xff0c;但成功相对来说更高一些。 第三方引用 在 2024 年 5 月 13 日&#xff0…

115页PPT华为管理变革:制度创新与文化塑造的核心实践

集成供应链&#xff08;ISC&#xff09;体系 集成供应链&#xff08;ISC&#xff09;体系是英文Integrated Supply Chain的缩写&#xff0c;是一种先进的管理思想&#xff0c;它指的是由相互间提供原材料、零部件、产品和服务的供应商、合作商、制造商、分销商、零售商、顾客等…

TCP simultaneous open测试

源代码 /*************************************************************************> File Name: common.h> Author: hsz> Brief:> Created Time: 2024年10月23日 星期三 09时47分51秒**********************************************************************…

ctfshow(175->178)--SQL注入--联合注入及其过滤

Web175 进入界面&#xff1a; 审计&#xff1a; 查询语句&#xff1a; $sql "select username,password from ctfshow_user5 where username !flag and id ".$_GET[id]." limit 1;";返回逻辑&#xff1a; if(!preg_match(/[\x00-\x7f]/i, json_enc…

可编辑PPT | 柔性制造企业数字化转型与智能工厂建设方案

这份PPT介绍了柔性制造企业在数字化转型和智能工厂建设方面的综合方案。探讨了数据采集、数字孪生、无码开发支撑、数据资产和应用能力层的构建&#xff0c;以及企业信息化的新思路。最终目标是通过这些技术和策略&#xff0c;实现供应链协同、产品全生命周期管理、绿色节能生产…