fork download
copy 
  1. //
  2. //  Brilliant - A Lot of Phi's.cpp
  3. //  programas2
  4. //
  5. //  Created by Lucca Siaudzionis on 20/06/14.
  6. //  Copyright (c) 2014 Luccasiau. All rights reserved.
  7. //
  8. #include <cstdio>
  9. #include <vector>
  10. #define MAXP 55050
  11. using namespace std;
  12.  
  13. int n;
  14. int mark[MAXP];
  15. vector<int> primes;
  16.  
  17. #define MODULO 1000000007
  18.  
  19. int isprime(int x){ //returns the smallest prime that divides X or returns 0 if X is prime
  20.  
  21.     //printf(":(\n");
  22.  
  23.     if(x == 2) return 0;
  24.  
  25.     for(int i = 0;i<primes.size();i++){
  26.  
  27.         if(primes[i]*primes[i] > x) break;
  28.  
  29.         if(x % primes[i] == 0) return primes[i];
  30.  
  31.     }
  32.  
  33.     return 0;
  34.  
  35. }
  36.  
  37. int maxexp(int d,int x){
  38.  
  39.     if(x % d) return 0;
  40.     return 1+(maxexp(d,x/d));
  41.  
  42. }
  43.  
  44. int phi_prime(int p,int exp){ //this consists of using phi(p^k) = (p-1)*p^(k-1)
  45.  
  46.     int aux = 1;
  47.     for(int i = 1;i<=exp-1;i++) aux *= p;
  48.  
  49.     return aux*(p-1);
  50.  
  51. }
  52.  
  53.  
  54. int phi(int x){ //recursive function to calculate phi(x)
  55.  
  56.     if(x <= 1) return 1;
  57.  
  58.     int turn = isprime(x);
  59.  
  60.     if(!turn) return x-1; //if x is a prime, phi(x) = x-1
  61.  
  62.     int exp = maxexp(turn,x);
  63.     int aux=1;
  64.     for(int i = 1;i<=exp;i++) aux *= turn;
  65.  
  66.     return phi_prime(turn,exp)*phi(x/aux); //this is true since phi is a multiplicative function
  67.  
  68. }
  69.  
  70.  
  71.  
  72. int main(){
  73.  
  74.     for(int i = 2;i<MAXP;i++){ // Builds 'primes' vector
  75.         if(!mark[i]){
  76.             primes.push_back(i);
  77.             for(int j = i+i;j<MAXP;j+=i) mark[j] = 1;
  78.         }
  79.     }
  80.  
  81.     int ANSWER = 0LL;
  82.     while( scanf("%d",&n) != EOF ){
  83.         ANSWER += phi(n);
  84.         ANSWER %= MODULO;
  85.     }
  86.  
  87.     printf("%d\n", ANSWER);
  88.  
  89.     return 0;
  90. }
Success #stdin #stdout 0s 3644KB
comments ()
stdin
copy 
Standard input is empty
stdout
copy 
0
https://ideone.com/4cHCPp
language:
C++ (gcc 8.3)
created:
10 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!