This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub ngthanhtrung23/ACM_Notebook_new
// This is only for calculating multiplicative functions // If we need a fast sieve, see SieveFast.h // From https://codeforces.com/blog/entry/54090 namespace linear_sieve { const int MN = 2e7; vector<int> primes; int smallest_p[MN]; // smallest_p[n] = smallest prime factor of n void linear_sieve_smallest_prime_factor(int n) { primes.clear(); memset(smallest_p, 0, sizeof smallest_p); for (int i = 2; i < n; ++i) { if (!smallest_p[i]) primes.push_back(i); for (int j = 0; j < int(primes.size()) && i * primes[j] < n; ++j) { smallest_p[i * primes[j]] = primes[j]; if (i % primes[j] == 0) break; } } } // Euler Phi {{{ bool is_composite[MN]; int phi[MN]; void linear_sieve_phi(int n) { memset(is_composite, false, sizeof is_composite); primes.clear(); phi[1] = 1; for (int i = 2; i < n; ++i) { if (!is_composite[i]) { primes.push_back(i); phi[i] = i - 1; // i is prime } for (int j = 0; j < (int) primes.size() && i * primes[j] < n; ++j) { is_composite[i * primes[j]] = true; if (i % primes[j] == 0) { phi[i * primes[j]] = phi[i] * primes[j]; //primes[j] divides i break; } else { phi[i * primes[j]] = phi[i] * phi[primes[j]]; //primes[j] does not divide i } } } } // }}} // Number of divisors {{{ int cnt_divisors[MN + 11]; // call linear_sieve_divisors(n+1) to init int cnt[MN + 11]; // power of smallest prime factor of i void linear_sieve_divisors(int n) { // init range [1, n-1] memset(is_composite, false, sizeof is_composite); primes.clear(); cnt_divisors[1] = 1; for (int i = 2; i < n; ++i) { if (!is_composite[i]) { primes.push_back(i); cnt[i] = 1; cnt_divisors[i] = 2; } for (int j = 0; j < (int) primes.size() && i * primes[j] < n; ++j) { int ip = i * primes[j]; is_composite[ip] = true; if (i % primes[j] == 0) { cnt[ip] = cnt[i] + 1; cnt_divisors[ip] = cnt_divisors[i] / (cnt[i] + 1) * (cnt[i] + 2); } else { cnt[ip] = 1; cnt_divisors[ip] = 2 * cnt_divisors[i]; } } } } // }}} }
#line 1 "Math/multiplicative_functions_linear.h" // This is only for calculating multiplicative functions // If we need a fast sieve, see SieveFast.h // From https://codeforces.com/blog/entry/54090 namespace linear_sieve { const int MN = 2e7; vector<int> primes; int smallest_p[MN]; // smallest_p[n] = smallest prime factor of n void linear_sieve_smallest_prime_factor(int n) { primes.clear(); memset(smallest_p, 0, sizeof smallest_p); for (int i = 2; i < n; ++i) { if (!smallest_p[i]) primes.push_back(i); for (int j = 0; j < int(primes.size()) && i * primes[j] < n; ++j) { smallest_p[i * primes[j]] = primes[j]; if (i % primes[j] == 0) break; } } } // Euler Phi {{{ bool is_composite[MN]; int phi[MN]; void linear_sieve_phi(int n) { memset(is_composite, false, sizeof is_composite); primes.clear(); phi[1] = 1; for (int i = 2; i < n; ++i) { if (!is_composite[i]) { primes.push_back(i); phi[i] = i - 1; // i is prime } for (int j = 0; j < (int) primes.size() && i * primes[j] < n; ++j) { is_composite[i * primes[j]] = true; if (i % primes[j] == 0) { phi[i * primes[j]] = phi[i] * primes[j]; //primes[j] divides i break; } else { phi[i * primes[j]] = phi[i] * phi[primes[j]]; //primes[j] does not divide i } } } } // }}} // Number of divisors {{{ int cnt_divisors[MN + 11]; // call linear_sieve_divisors(n+1) to init int cnt[MN + 11]; // power of smallest prime factor of i void linear_sieve_divisors(int n) { // init range [1, n-1] memset(is_composite, false, sizeof is_composite); primes.clear(); cnt_divisors[1] = 1; for (int i = 2; i < n; ++i) { if (!is_composite[i]) { primes.push_back(i); cnt[i] = 1; cnt_divisors[i] = 2; } for (int j = 0; j < (int) primes.size() && i * primes[j] < n; ++j) { int ip = i * primes[j]; is_composite[ip] = true; if (i % primes[j] == 0) { cnt[ip] = cnt[i] + 1; cnt_divisors[ip] = cnt_divisors[i] / (cnt[i] + 1) * (cnt[i] + 2); } else { cnt[ip] = 1; cnt_divisors[ip] = 2 * cnt_divisors[i]; } } } } // }}} }