hdu2824 The Euler function O(n)求欧拉函数

我就是我 2021-12-14 12:07 191阅读 0赞

hdu2824 The Euler function

O(n)求欧拉函数

1 #include <bits/stdc++.h> 
     2 #define ll long long 
     3 using namespace std ; 
     4 
     5 const int N = 3000011 ; 
     6 int l,r ; 
     7 int prime[ 300011 ],phi[N] ;  
     8 ll sum ; 
     9 bool f[N] ; 
    10 
    11 inline void Euler_init(int NN)  
    12 {
    13     phi[ 1 ] = 1 ; f[ 1 ] = 1 ; 
    14     prime[ 0 ] = 0 ; 
    15     for(int i=2;i<=NN;i++) 
    16     {
    17         if( !f[ i ] ) prime[++prime[0]] = i,phi[ i ] = i-1 ; 
    18         for(int j=1;j<=prime[ 0 ] && i*prime[ j ]<=NN;j++) 
    19         {
    20             f[ i*prime[ j ] ] = 1 ; 
    21             if( i%prime[ j ] == 0 ) 
    22             {
    23                 phi[ i*prime[ j ] ] = phi[ i ] * prime[ j ] ; 
    24                 break ; 
    25             }
    26             else phi[ i*prime[ j ] ] = phi[ i ] * (prime[ j ]-1) ; 
    27         }
    28     }
    29 }
    30 
    31 int main() 
    32 {
    33     Euler_init(3000000) ;   
    34     
    35     while(~scanf("%d%d",&l,&r)) 
    36     {
    37         sum = 0 ; 
    38         for(int i=l;i<=r;i++) 
    39             sum = sum + phi[ i ] ; 
    40         printf("%lld\n",sum) ; 
    41     }    
    42     return 0 ; 
    43 }

转载于:https://www.cnblogs.com/third2333/p/7182391.html

发表评论取消回复

表情：

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

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

相关阅读

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

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

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

相关 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 赞/ 162 阅读

相关 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 阅读

相关 The Euler function

题目描述： Problem Description The Euler function phi is an important kind of function in n

﹏ヽ暗。殇╰゛Y/ 2022年03月18日 02:50/ 0 赞/ 121 阅读

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

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

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

相关 hdu2824 The Euler function O(n)求欧拉函数

hdu2824 The Euler function O(n)求欧拉函数 1 include <bits/stdc++.h> 2 define ll l

我就是我/ 2021年12月14日 12:07/ 0 赞/ 192 阅读

相关 hdu 2824 The Euler function

hdu 2824 The Euler function 题意源代码题意给定两个数a,b,求[a,b]区间欧拉函数的和 ps：欧拉

柔光的暖阳◎/ 2021年10月13日 01:33/ 0 赞/ 193 阅读

相关 HDU - 6322 - Problem D. Euler Function 【欧拉函数 + 规律】题解

目录 1.题目 2.代码 1.题目 In number theory, Euler’s totient fu

叁歲伎倆/ 2021年07月25日 00:07/ 0 赞/ 326 阅读

相关数论 - 欧拉函数【普通求法 + 筛法求欧拉函数】

欧拉函数 1.定义对于正整数n,欧拉函数是小于或等于n的正整数中(即1-n中)与n互质的数的数目，记作φ(n) 其中φ(1)=1。 2求n的

向右看齐/ 2021年07月24日 23:53/ 0 赞/ 440 阅读

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

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

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