HDU——2588 GCD
2024-08-30 23:00:38
题目大意:
求1~N中与N的最大公约数大于M的个数
思路:
这个题是不是可以想到暴力枚举??对于每一组数据枚举与他的最大公约数大于m的数的个数。
是,这种做法没错误,但是保准你T成狗。。。。
我们至少要找一个不T的做法吧。。。我们考虑gcd这样一个性质gcd(x,y)=m则gcd(x/m,y/m)=1;我们就可以轻易的发现在这个地方的x/m不就是我们要求的第一个式子中的x吗??这样我们就只需要统计这样的x/m的个数不就好了吗?!
这样显然就可以知道,这不就是欧拉函数吗?!
是的,那我们就来尝试一下吧。。
代码:
#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int t,n,m,ans; int read() { ,f=; char ch=getchar(); ; ch=getchar();} +ch-'; ch=getchar();} return x*f; } int get_phi(int x) { int sum=x; ==) { ==) x/=; sum/=; } ;i*i<=x;i+=) { ) { ) x/=i; sum=sum/i*(i-); } } ) sum=sum/x*(x-); return sum; } int main() { t=read(); while(t--) { n=read(),m=read();ans=; for(int i=m;i<=n;i++) { ) ans+=get_phi(n/i); } printf("%d\n",ans); } return ans; }
有没有发现这样完美的T成狗了。。。
哈哈,我们在考虑一下别的优化。
跟上一个题一样,我们可以发现能成为他的最大公约数的数是不是一定是她的因子??我们求它大于m的因子可以暴力枚举能被他整除得数。
好像照样T。。。。
我们想一下上一题我们怎么处理的。我们是不是处理的根n?! 对于我们处理出来的因子是不是有两个来源,一个是本身i,另一个是n/i??
这样我们就可以分两种情况来判断,一是i>m,另一种是n/i大于m,这样我们再求n/i的欧拉函数与n/n/i即i的欧拉函数就好了。
#include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int t,n,m,ans; int read() { ,f=; char ch=getchar(); ; ch=getchar();} +ch-'; ch=getchar();} return x*f; } int get_phi(int x) { int sum=x; ==) { ==) x/=; sum/=; } ;i*i<=x;i+=) { ) { ) x/=i; sum=sum/i*(i-); } } ) sum=sum/x*(x-); return sum; } int main() { t=read(); while(t--) { n=read(),m=read();ans=; ;i*i<=n;i++) { ) { if(i>=m&&i*i!=n) ans+=get_phi(n/i); if(n/i>=m) ans+=get_phi(i); } } printf("%d\n",ans); } return ans; }
最新文章
- jQuery可自动播放动画焦点图插件Koala
- php redis 安装篇(windows 7)
- 【编程题目】输入一个单向链表,输出该链表中倒数第 k 个结点
- 通过 CALayer 修改 UIImageView 的界面属性
- ServiceStack.Hello——跨平台.net REST api服务搭建
- 读改善c#代码157个建议:建议1~3
- 具体分析Struts工作流程
- Android之Http沟通——4.Android HTTP索取信息:HttpClient
- 2015 ACM/ICPC Asia Regional Changchun Online
- c#.net的网站出现“正在中止线程””异常的原因和解决方法
- 数据源C3P0配置
- GET方式提交中文编码问题以及三种解决方式
- android自定义Notification通知栏实例
- 【BZOJ2576】[JSOI2011]序的计数 (动态规划)
- 用Python优雅的处理日志
- Learning-MySQL【6】:视图、触发器、存储过程、函数、流程控制
- 使用Git上传项目到Gitee
- 分享《机器学习实战基于Scikit-Learn和TensorFlow》中英文PDF源代码+《深度学习之TensorFlow入门原理与进阶实战》PDF+源代码
- 学习Spring Boot:(二十五)使用 Redis 实现数据缓存
- springMVC :interceptors
热门文章
- [读书笔记1]《C语言嵌入式系统编程修炼》
- 平方分割poj2104K-th Number
- 题解报告:hdu 1061 Rightmost Digit(快速幂取模)
- Json-->;Newton.Json.dll的使用方法
- Android 仿淘宝头条竖直跑马灯式新闻标题及“分页思想
- PHP常见问题总结
- lsb_release No LSB modules are available
- sql常用手法(二)
- Android中ProgressDialog自动消失
- 1043 输出PATest (20 分)