hdu 3501（欧拉函数引申）

骑猪看日落 2021-12-21 01:09 228阅读 0赞

题意：求小于N与N不互质的数的和  
欧拉公式的引伸：小于或等于n的数中，与n互质的数的总和为：φ(x) \* x / 2。(n>1)

1 #include<iostream>
     2 #include<string.h>
     3 #include<string>
     4 #include<sstream>
     5 #include<vector>
     6 #include<deque>
     7 #include<map>
     8 #include<algorithm>
     9 #include<iomanip>
    10 #include<math.h>
    11 #include<set>
    12 using namespace std;
    13 
    14 typedef long long ll;
    15 typedef unsigned long long ull;
    16 const int mod = 1000000007;
    17 ll Eular(ll n)
    18 {
    19     ll res = n;
    20     if (n == 1)
    21         return 1;
    22     for (int i = 2; i*i <= n; i++)
    23     {
    24         if (n%i == 0)
    25         {
    26             res = res / i * (i - 1);
    27             while (n%i == 0)
    28                 n = n / i;
    29         }
    30     }
    31     if (n != 1)
    32     {
    33         res = res / n * (n - 1);
    34     }
    35     return res;
    36 }
    37 int main()
    38 {
    39     ll n;
    40     while (cin >> n&&n)
    41     {
    42         
    43         ll ans = ((n - 1)*n / 2%mod - Eular(n)*n / 2 % mod +mod) %mod;
    44         cout << ans << endl;
    45     }
    46     return 0;
    47 }

转载于:https://www.cnblogs.com/QingFengDaHui/p/10389521.html

发表评论取消回复

表情：

评论列表（有 0 条评论，228人围观）

还没有评论，来说两句吧...

相关阅读

相关欧拉函数 AcWing 873. 欧拉函数

欧拉函数 AcWing 873. 欧拉函数原题链接 [AcWing 873. 欧拉函数][AcWing 873.] 算法标签数学知识欧拉函数思路

绝地灬酷狼/ 2023年09月28日 11:38/ 0 赞/ 114 阅读

相关欧拉函数

欧拉函数对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。例如euler(8)=4，因为1,3,5,7均和8互质。 Euler函数表达通式：euler(x)

待我称王封你为后i/ 2022年07月29日 08:47/ 0 赞/ 223 阅读

相关欧拉函数

欧拉函数对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。例如euler(8)=4，因为1,3,5,7均和8互质。 Euler函数表达通式：euler(x)

向右看齐/ 2022年07月19日 01:23/ 0 赞/ 198 阅读

相关欧拉函数

欧拉函数在数论中指的是，对于正整数N,小于或等于N (\[1,N\]),且与N互质的正整数(包括1)的个数，记作φ(n)。以下是欧拉函数的模板 1，直接求φ(n

短命女/ 2022年06月12日 02:58/ 0 赞/ 199 阅读

相关 hdu -2837(指数循环节+欧拉函数)

Problem Description Assume that f(0) = 1 and 0^0=1. f(n) = (n%10)^f(n/10) for all n big

àì夳堔傛蜴生んèń/ 2022年06月10日 13:14/ 0 赞/ 160 阅读

相关【欧拉函数】

1.1欧拉函数定义首先，需要理解一下什么是欧拉函数，欧拉函数phi(n)的定义为小于等于n且与n互素的整数个数。那么什么是互素呢？互素是指对于两个数a和b，a和b的最大公

雨点打透心脏的1/2处/ 2022年06月09日 00:40/ 0 赞/ 267 阅读

相关欧拉函数

定义在数论，对正整数n，欧拉函数是小于或等于n的正整数中与n互质的数的数目（φ(1)=1），例如φ(8)=4，因为1,3,5,7均和8互质。通式 ![70][

落日映苍穹つ/ 2022年05月16日 07:58/ 0 赞/ 272 阅读

相关 HDU 2824 The Euler function (欧拉函数)

The Euler function Time Limit : 2000/1000ms (Java/Other) Memory Limit : 32768/32768K

雨点打透心脏的1/2处/ 2022年03月29日 05:48/ 0 赞/ 134 阅读

相关 hdu 3501（欧拉函数引申）

题意：求小于N与N不互质的数的和欧拉公式的引伸：小于或等于n的数中，与n互质的数的总和为：φ(x) \ x / 2。(n>1) 1 include<iostre

骑猪看日落/ 2021年12月21日 01:09/ 0 赞/ 229 阅读

相关 HDU - 1787 - GCD Again 【欧拉函数】题解

目录 1.题目 2.代码 1.题目 Do you have spent some time to think

超、凢脫俗/ 2021年07月24日 12:59/ 0 赞/ 347 阅读