BZOJ 2705 [SDOI2012]Longge的问题
发布日期:2021-07-27 13:45:09
浏览次数:1
分类:技术文章
本文共 845 字,大约阅读时间需要 2 分钟。
Description
Longge的数学成绩非常好,并且他非常乐于挑战高难度的数学问题。现在问题来了:给定一个整数N,你需要求出∑gcd(i, N)(1<=i <=N)。
Input
一个整数,为N。
Output
一个整数,为所求的答案。
Sample Input
6
Sample Output
15
HINT
【数据范围】
对于60%的数据,0< N<=2^16。
对于100%的数据,0< N<=2^32。
枚举n 的所有因子,然后想办法统计出来所有的和 n 的最大公约数正好是这个因子的数的个数,之后乘上这个因子,最后累加,就是需要的答案了。
详见
#include#include #include using namespace std;long long ans,n;long long phi(long long x){ long long ans=x,tp=sqrt(1.0*x); for(long long i=2;i<=tp;i++) if(x%i==0) { ans-=ans/i; while(x%i==0) x/=i; } if(x>1) ans-=ans/x; return ans;}int main(){ scanf("%lld",&n); long long tp=sqrt(1.0*n); for(long long i=1;i<=tp;i++) if(n%i==0) ans+=i*phi(n/i)+n/i*phi(i); if(tp*tp==n) ans-=tp*phi(tp); printf("%lld\n",ans); return 0;}
转载地址:https://blog.csdn.net/Rlt1296/article/details/51885296 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过,博主的博客真漂亮。。
[***.116.15.85]2024年03月31日 00时42分29秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
【C++】算法集锦(10)通俗讲kmp算法
2019-04-27
【C++】算法集锦(12):高楼扔鸡蛋
2019-04-27
【图解】拥塞控制
2019-04-27
线程上下文切换
2019-04-27
什么是服务熔断?
2019-04-27
服务器压力过大?CPU打满?我来帮你快速检查Linux服务器性能
2019-04-27
C++面经总结之《Effective C++》(一)
2019-04-27
C++面经总结之《Effective C++》(二)
2019-04-27
这是什么“虎狼之词”啊!!!程序员的健康问题,看一线老中医怎么说!!!
2019-04-27
打开我的收藏夹 -- Python数据分析杂谈
2019-04-27
上手Pandas,带你玩转数据(1)-- 实例详解pandas数据结构
2019-04-27
上手Pandas,带你玩转数据(2)-- 使用pandas从多种文件中读取数据
2019-04-27
上手Pandas,带你玩转数据(3)-- pandas数据存入文件
2019-04-27
爬虫遇上不让右击、不让F12的网站,该怎么办?
2019-04-27
上手Pandas,带你玩转数据(4)-- 数据清洗
2019-04-27
上手Pandas,带你玩转数据(5)-- 数据转换与数据定位
2019-04-27
上手Pandas,带你玩转数据(6)-- 摆脱对pandas可视化丑图的刻板印象吧
2019-04-27