【POJ 2480】Longge's problem(欧拉函数)
函数 39 poj Problem 欧拉
2023-09-11 14:19:25 时间
题意
求$ \sum_{i=1}^n gcd(i,n) $ 给定 $n(1\le n\le 2^{32}) $。
题解
欧拉函数 $φ(x)$ :1到x-1有几个和x互质的数。
gcd(i,n)必定是n的一个约数。
若p是n的约数,那么gcd(i,n)==p的有$φ(n/p)$个数,因为要使gcd(i,n)==p,i/p和n/p必须是互质的。
那么就是求i/p和n/p互质的i在[1,n]里有几个,就等价于 1/p,2/p,...,n/p 里面有几个和n/p互质,即φ(n/p)。
求和的话,约数为p的有φ(n/p),所以就是p*φ(n/p),同时把约数为n/p的加上去,i*i==n特判一下。
#include<cstdio> #include<cmath> #define ll long long ll n,ans,i; ll euler(int x) { int res=x; for(int i=2; i<=sqrt(x); i++) if(x%i==0) { res=res/i*(i-1); while(x%i==0)x/=i; } if(x>1)res=res/x*(x-1); return res; } int main() { while(~scanf("%lld",&n)) { ans=0; for(i=1; i<sqrt(n); i++)if(n%i==0) ans+=i*euler(n/i)+n/i*euler(i); if(i*i==n)ans+=i*euler(i); printf("%lld\n",ans); } }
另外一种做法是:
素数a有$φ(a^b)=a^b-a^(b-1)=(a-1)*a^b$。
且有 $\sum_{i=1}^n gcd(i,a^b)$
$=φ(a^b)+a*φ(a^(b-1))+...+(a^b)*φ(1)$
$=b*(a-1)*(a^(b-1))+a^b$。
由$n=p_1^{k_1}+p_2^{k_2}+...+p_s^{k_s}$,
可得$\sum_{i=1}^n gcd(i,n)$
$=\sum_{i=1}^n gcd(i,p_1^{k_1})*\sum_{i=1}^n gcd(i,p_2^{k_2})*...*\sum_{i=1}^n gcd(i,p_s^{k_s})$
(我觉得这个理解起来不容易)。
#include<cstdio> long long n,i,k,pk,ans; int main () { while(scanf("%lld",&n)!=EOF) { ans=1; for(i=2;i*i<=n;++i) { k=0,pk=1; while(n%i==0) { n=n/i; k++; pk*=i; } ans*=k*(pk-pk/i)+pk;//φ[p^k]=k×(p^k-p^(k-1))+p^k } if(n>1)ans*=2*n-1; printf("%lld\n",ans); } return 0; }
相关文章
- VB6 如何添加自定义函数 模块 把代码放到一个模块中
- SAS中的cmiss函数
- 借力阿里云函数计算极致弹性,石墨文档助力 20 万家企业远程复工
- VueUse常用函数介绍
- ORB-SLAM2 ---- KeyFrameDatabase::DetectRelocalizationCandidates函数
- Atitit 函数式编程与命令式编程的区别attilax总结 qbf
- Atitit.跨平台预定义函数 魔术方法 魔术函数 钩子函数 api兼容性草案 v2 q216 java c# php js.docx
- C++:C++编程语言学习之函数的定义/调用/嵌套/回归的简介、案例应用之详细攻略
- Py之seaborn:数据可视化seaborn库(一)的柱状图、箱线图(置信区间图)、散点图/折线图、核密度图/等高线图、盒形图/小提琴图/LV多框图实现的十二个函数源代码详解之最强攻略(建议收藏)
- Qt中使用匿名函数lambda表达式
- JavaScript的最大函数參数长度和最大栈深度检測
- scala本地调试函数
- 使用tp访问数据库时提示错误: 'PDO' not found, 和not defined constant mysql_attr_init_command 和call an undefined function ThinkTemplatesimpleXml_load_string()函数
- 【SQL开发实战技巧】系列(四十三):Oracle12C常用新特性☞转换函数的增强和不可见字段