• API
• FAQ
• Tools
• Archive
daily pastebin goal
44%
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.

Top