首页 > 代码库 > HDU 3501 Calculation 2(欧拉函数的应用)
HDU 3501 Calculation 2(欧拉函数的应用)
HDU 3501 Calculation 2
大意:求1~n之间与n不互质的数的总和。
思路:欧拉函数的应用;先用欧拉函数求出与n互质的总数m,计算m个数的总和,用n的总和减去m的总和就是想要的结果。
1 #include <stdio.h> 2 #define LL __int64 3 4 int eular(int n){ 5 int ret = 1; 6 for(int i = 2; i*i <= n;i++) 7 if(n%i == 0){ 8 n /= i, ret *= i-1; 9 while(n%i == 0) 10 n /= i, ret *= i; 11 } 12 if(n > 1) 13 ret *= n-1; 14 return ret; 15 } 16 17 LL n, m; 18 19 int main() 20 { 21 while(~scanf("%I64d", &n) && n) 22 { 23 LL sum = n*(n+1)/2-n; ///计算所有数总数 24 LL t = eular(n)*n/2; ///计算互质的数总和 25 sum -= t; 26 sum %= 1000000007; 27 printf("%I64d\n", sum); 28 } 29 30 return 0; 31 }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。