fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. using ll = long long;
  5.  
  6. /*
  7.     1'den max_power'a kadarki her p için:
  8.         p * 1, p * 2, ..., p * bound
  9.     Kaç farklı sayı olduğunu buluyor.
  10.     (Inclusion-exclusion)
  11.  
  12.     mn, EKOK'u alınan sayılara dahil olan en küçük sayı.
  13.     mn == 1e9 demek hiç sayı seçmemişiz demek.
  14. */
  15. ll solve_for_mask(int max_power, int bound, int i = 1, ll lcm = 1, int coef = -1, int mn = 1e9) {
  16.     if (lcm > bound) // 0 gelecektir her türlü.
  17.         return 0;
  18.  
  19.     if (i == max_power + 1) {
  20.         if (mn == 1e9)
  21.             return 0;
  22.  
  23.         // Ortak sayılar (mn * bound)'a kadar olacaktır.
  24.         return (ll)coef * mn * bound / lcm;
  25.     }
  26.  
  27.     ll without = solve_for_mask(max_power, bound, i + 1, lcm, coef, mn);
  28.     lcm = lcm / __gcd(lcm, (ll)i) * i;
  29.     ll with = solve_for_mask(max_power, bound, i + 1, lcm, -coef, mn == 1e9 ? i : mn);
  30.     return without + with;
  31. }
  32.  
  33. /*
  34.     n = a^k
  35.     En küçük a > 0 için {a, k} döndürüyor.
  36. */
  37. array<int, 2> get_mask(int n) {
  38.     int init_n = n;
  39.     vector<array<int, 2>> factorization;
  40.     int g = 0;
  41.     for (int i = 2; i * i <= n; i++) {
  42.         if (n % i)
  43.             continue;
  44.         int exp = 0;
  45.         while (n % i == 0)
  46.             n /= i, exp++;
  47.         factorization.push_back({i, exp});
  48.         g = __gcd(g, exp);
  49.     }
  50.     if (n > 1) {
  51.         return {init_n, 1};
  52.     }
  53.  
  54.     int mask = 1;
  55.     for (auto &[prime, exp] : factorization) {
  56.         for (int i = 0; i < exp / g; i++)
  57.             mask *= prime;
  58.     }
  59.  
  60.     return {mask, g};
  61. }
  62.  
  63. int main() {
  64.     int a1, a2, b1, b2;
  65.     cin >> a1 >> a2 >> b1 >> b2;
  66.     vector<int> max_powers(a2 + 1);
  67.     for (int a = a1; a <= a2; a++) {
  68.         auto [mask, exp] = get_mask(a);
  69.         max_powers[mask] = exp;
  70.     }
  71.     ll ans = 0;
  72.     for (int max_power : max_powers) {
  73.         ans += solve_for_mask(max_power, b2) - solve_for_mask(max_power, b1 - 1);
  74.     }
  75.     cout << ans << "\n";
  76. }
Success #stdin #stdout 0.01s 5292KB
comments (?)
stdin
copy 
2 3000 2 3000
stdout
copy 
8887842
https://ideone.com/SwDp80
language:
C++14 (gcc 8.3)
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!