fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. // n log(n)
  6. // sqrt(n)
  7. int totientFunc(int n) {
  8.     int ans = 0;
  9.     for (int i=1; i<=n; i++) {
  10.         if (__gcd(n, i) == 1) ans++;
  11.     }
  12.     return ans;
  13. }
  14.  
  15. const int N = 10000000;
  16. vector<int> lp(N+1);
  17. vector<int> pr;
  18.  
  19. // linear sieve 
  20. void init() {
  21.     for (int i=2; i <= N; ++i) {
  22.         if (lp[i] == 0) {
  23.             lp[i] = i;
  24.             pr.push_back(i);
  25.         }
  26.         for (int j = 0; i * pr[j] <= N; ++j) {
  27.             lp[i * pr[j]] = pr[j];
  28.             if (pr[j] == lp[i]) {
  29.                 break;
  30.             }
  31.         }
  32.     }
  33.  
  34. }
  35.  
  36. // Complexity = O(log(n))
  37. int impTF(int n) {
  38.     int phi = n;
  39.     while(n > 1){
  40.         int p = lp[n]; // p = lp[5] = 5
  41.         phi -= phi / p; // phi = 40 - 40 / 5 = 32
  42.         int power = 0;
  43.         while (n % p == 0) n /= p, power++; // Can run at most log(n)
  44.     }
  45.  
  46.     return phi;
  47. }
  48. // Find the TF for all numbers between 1 to n
  49. // O (n * log(n))
  50. // Optimized way = O(n * log (log (n)))
  51.  
  52. int divCount(int n) {
  53.     int ans = 1;
  54.     while(n > 1){
  55.         int p = lp[n];
  56.         int power = 0;
  57.         while (n % p == 0) n /= p, power++; // Can run at most log(n)
  58.         ans = ans * (power + 1);
  59.     }
  60.     return ans;
  61. }
  62.  
  63. void phi_1_to_n(int n) {
  64.     vector<int> phi(n + 1);
  65.     for (int i = 0; i <= n; i++)
  66.         phi[i] = i;
  67.  
  68.     for (int i = 2; i <= n; i++) {
  69.         if (phi[i] == i) { // i = 2, phi[2] = 2
  70.             for (int j = i; j <= n; j += i) // j = 2; j<=n; j+=2
  71.                 phi[j] -= phi[j] / i;
  72.         }
  73.     }
  74. }
  75.  
  76. int main( ) {
  77.     init();
  78.     cout << totientFunc(120000) << endl;
  79.     cout << impTF(120000) << endl;
  80.  
  81. }
  82.  
  83. /*
  84.     Find all prime factors of 120 = 2 ^ 3 * 3 * 5
  85.     Result = [2] + [3, 5] = [2, 3, 5]
  86.     lp[120] = 2
  87.     120 / 2 = 60
  88.     60 / 2 = 30
  89.     30 / 2 = 15
  90.     lp[15] = 3
  91.     15 / 3 = 5
  92.     lp[5] = 5
  93. */
  94.  
  95.  
  96. #include <bits/stdc++.h>
  97. using namespace std;
  98.  
  99. int main() {
  100.     int n;
  101.     cin >> n;
  102.  
  103.     for (int i=0; i<n; i++) {
  104.         int x;
  105.         cin >> x;
  106.         int ans = 0;
  107.         for (int j=1; j*j <= x; j++) {
  108.             if (x % j == 0) {
  109.                 ans++; 
  110.                 if (j != (x / j)) ans++;
  111.             }
  112.         }
  113.         cout << ans << endl;
  114.     }
  115. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:99:5: error: redefinition of 'main'
int main() {
    ^
prog.cpp:76:5: note: previous definition is here
int main( ) {
    ^
1 error generated.
stdout
copy 
Standard output is empty
https://ideone.com/tKiSTS
language:
C++14 (clang 8.0)
created:
1 year 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!