fork download
copy 
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. /*
  6.     n = a^k
  7.     En küçük a > 0 için {a, k} döndürüyor.
  8. */
  9. array<int, 2> get_mask(int n) {
  10.     int init_n = n;
  11.     vector<array<int, 2>> factorization;
  12.     int g = 0;
  13.     for (int i = 2; i * i <= n; i++) {
  14.         if (n % i)
  15.             continue;
  16.         int exp = 0;
  17.         while (n % i == 0)
  18.             n /= i, exp++;
  19.         factorization.push_back({i, exp});
  20.         g = __gcd(g, exp);
  21.     }
  22.  
  23.     if (n > 1) {
  24.         return {init_n, 1};
  25.     }
  26.  
  27.     int mask = 1;
  28.     for (auto &[prime, exp] : factorization) {
  29.         for (int i = 0; i < exp / g; i++)
  30.             mask *= prime;
  31.     }
  32.  
  33.     return {mask, g};
  34. }
  35.  
  36. int main() {
  37.     int a1, a2, b1, b2;
  38.     cin >> a1 >> a2 >> b1 >> b2;
  39.     set<int> existing_powers[a2 + 1];
  40.     for (int a = a1; a <= a2; a++) {
  41.         auto [mask, exp] = get_mask(a);
  42.         for (int b = b1; b <= b2; b++)
  43.             existing_powers[mask].insert(exp * b);
  44.     }
  45.     int ans = 0;
  46.     for (auto &powers : existing_powers)
  47.         ans += powers.size();
  48.     cout << ans << "\n";
  49. }
Success #stdin #stdout 0.81s 420308KB
comments (?)
stdin
copy 
2 3000 2 3000
stdout
copy 
8887836
https://ideone.com/XiEJoi
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!