And the same code in C++.
#include <cstdio> #include <vector> #include <set> using namespace std; long distinct_powers(long n) { long c = 0; vector<bool> tested(n+1, false); for (long a = 2; a <= n; a++) if (!tested[a]) { set<long> s; for (long _a = a*a, pw = 2; _a <= n; _a *= a, pw++) { tested[_a] = true; for (long b = 2, bxpw = b*pw; b <= n; b++, bxpw += pw) if (bxpw > n) s.insert(bxpw); } c += s.size() + n-1; } return c; } int main() { long n; scanf("%ld", &n); printf("%ld\n", distinct_powers(n)); return 0; }
This was a bit of a rabbit hole, definitely not an "easy" task. Here's the code. The idea is for each base to iterate through its powers e.g. for 2 iterate through 4, 8, 16, ... . Create a set of exponents for each power e.g. for 8 we have 8^2=2^6, 8^3=2^9, ... and therefore exponents will be 6, 9, .. . Then merge all sets. Don't do sets for the bases though to avoid timeout.
def distinct_terms(n: int) -> int: count = 0 tested = [0]*(n+1) for a in range(2, n+1): if tested[a]: continue; combined = set() pw = 2 while (a**pw <= n): tested[a**pw] = True s = set([b*pw for b in range(2, n+1) if b*pw > n]) combined.update(s) pw += 1 count += len(combined) + n-1 return count print(distinct_terms(int(input())))
Nice challenge. For those who are struggling like I did. I counted the maximum Exponent number and then checked if b can be combined by any number below this max exponent. For example 8 = 2^3 so 8^b can be combined by 2^1*c or 2^2*d.
int findMaxExponent(int num) { int root = sqrt(num); if(root == 1) return 1; for(int i = 2; i <= root; i++) { int cached_num = num; int expo_count = 1; while(cached_num % i == 0) { expo_count++; cached_num /= i; if(cached_num == i) { return expo_count; } } } return 1; }
Easy, really? Two whole days and I haven't managed to find a O(1) solution. Used double memorization and some optimization. Final timing for N=100000 is 0.2 seconds.
Blimey, that was pretty tough. No way an easy problem.
Sort 41 Discussions, By:
Please Login in order to post a comment