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