SHARE
TWEET

Untitled

a guest Feb 22nd, 2019 65 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <cmath>
  5. #include <set>
  6. #include <map>
  7.  
  8. using namespace std;
  9.  
  10. vector<int> generate_primes(int range, bool* seive) {
  11.     fill(seive, seive + range, true);
  12.     for (int i = 2; i < sqrt(range); i++) {
  13.         if (seive[i] == true) {
  14.             for (int j = i * 2; j < range; j += i) {
  15.                 seive[j] = false;
  16.             }
  17.         }
  18.     }
  19.     vector<int> result;
  20.     for (int i = 2; i < range; i++) {
  21.         if (seive[i]) {
  22.             result.push_back(i);
  23.         }
  24.     }
  25.     return result;
  26. }
  27.  
  28. int gcd(int a, int b) {
  29.     return b == 0 ? a : gcd(b, a % b);
  30. }
  31.  
  32. int main() {
  33.     int a0 = 2, a1 = 100, b0 = 2, b1 = 100;
  34.     bool seive[a1 + 1]; // seive[x] is true for prime x
  35.     vector<int> primes = generate_primes(a1 + 1, seive);
  36.     set<pair<int, int>> values; // pairs of <a, b> that give unique a^b
  37.  
  38.     for (int a = a0; a <= a1; a++) {
  39.         int _a = a;
  40.         map<int, int> primes_count; // key: prime multiplier of a, value: count of such multipliers
  41.         while (!seive[_a]) {
  42.             for (size_t i = 0; i < primes.size(); i++) {
  43.                 if (_a % primes[i] == 0) {
  44.                     primes_count[primes[i]]++;
  45.                     _a /= primes[i];
  46.                     break;
  47.                 }
  48.             }
  49.         }
  50.         primes_count[_a]++;
  51.  
  52.         // find max power to represent a:
  53.         int to_power = primes_count.begin()->second;
  54.         for (auto it = primes_count.begin()++; it != primes_count.end(); ++it) {
  55.            to_power = gcd(to_power, it->second);
  56.         }
  57.  
  58.         // find base for such power:
  59.         int base = 1;
  60.         for (auto it = primes_count.begin(); it != primes_count.end(); ++it) {
  61.             base *= pow(it->first, (it->second) / to_power);
  62.         }
  63.  
  64.         for (int b = b0; b <= b1; b++) {
  65.             values.insert(make_pair(base, to_power * b));
  66.         }
  67.    
  68.     }
  69.  
  70.     cout << values.size() << endl;
  71.  
  72.     return 0;
  73. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top