- 1
- #include
- 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
- }
来源: http://www.bubuko.com/infodetail-2171304.html