Untitled
unknown
plain_text
3 years ago
1.7 kB
2
Indexable
Never
#include <iostream> #include <vector> #include <chrono> using namespace std; using namespace std::chrono; const int kMaxN = 1e8; vector<int> phi(kMaxN + 1, 0); void CalcPhi2() { phi[1] = 1; for (int n = 2; n <= kMaxN; ++n) { if (phi[n] != 0) continue; long long diff = n - 1; for (long long p = n; p <= kMaxN; p *= n) { for (int c = 0; c * p * n <= kMaxN; ++c) { long long val = c * p * n; for (int k = 1; k < n && p * (c * n + k) <= kMaxN; ++k) { if (phi[c * n + k] == 0) continue; phi[val + p * k] = phi[c * n + k] * diff; } } diff *= n; } } } void CalcPhi3() { phi[1] = 1; for (int n = 2; n <= kMaxN; ++n) { if (phi[n] != 0) continue; int diff = n - 1; for (long long p = n; p <= kMaxN; p *= n) { for (int c = 1; c * p <= kMaxN; c++) { int val = c * p; if (phi[c] == 0) continue; phi[val] = diff * phi[c]; } diff *= n; } } } int main() { auto start = high_resolution_clock::now(); CalcPhi3(); auto stop = high_resolution_clock::now(); auto duration = duration_cast<microseconds>(stop - start); int n; cin >> n; long long sum = 0; for (int i = 1; i <= n; ++i) { sum += phi[i]; if (i % 100 == 0) { sum = 0; } } if (sum != 0) { cout << sum << " "; } cout << endl; cout << "Time taken by function: " << duration.count() / 1000000. << " seconds" << endl; return 0; }