pabloskimg's blog

By pabloskimg, history, 5 years ago,

Basically the title. The problem statement can be found here. No idea how to solve it efficiently.

UPDATE 2: based on the answers so far, the solution would be to exhaustively explore all combinations of exponents k1, k2, ..., kr (ki ≥ kj for all i < j) such that and k = 2k1 * 3k2 * 5k3 * 7k4 * 11k5 * ... < 263. During the exhaustive search one can map each n to its minimum k found (for instance, using an unordered_map) and then the queries can be answered in O(1). The problem is: how can you estimate the complexity of the exhaustive search? Any easy way to estimate an upperbound for it?

UPDATE 3: pshishod2645 says there are around 2 * 106 valid combinations of exponents, where did he get that number from?

• -24

 » 5 years ago, # |   0 Let the prime factorisation of n be p1n1p2n2....pknk, then we have , which means that f(n) doesn't depend on primes but instead on the exponents. So you can find all numbers ( < 263)which are formed by first few primes, Mathematically , you have to find all such numbers such that if the prime factorisation of n contains prime p, then it must contains all primes less than p. The number of such numbers is around 2 * 106, so you preprocess f(n) for all those n and get the answer for all given n in O(1). My code for finding such numbers is in spoliler Spoiler/* A story, which will never end A story, which never began */ #include using namespace std; #define IOS ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0) #define endl '\n' #define ll long long vector v, prime; const int N = 100; __int128 MAX = 1; void find(int id, __int128 num){ if(num > MAX)return; v.push_back(num); while(num < MAX){ num = num*prime[id]; find(id + 1, num); } } void sieve(){ int vis[N]; fill(vis, vis + N, 0); for(int i=2;i
•  » » 5 years ago, # ^ | ← Rev. 3 →   0 "So you can find all numbers (< 2^63) which are formed by first few primes" What do you mean by first few primes? Which are those first few primes?"you have to find all such numbers such that if the prime factorisation of n contains prime p, then it must contains all primes less than p" Why do I have to find these numbers?Would you mind elaborating your points a little more?
•  » » » 5 years ago, # ^ |   0 The value of f(n) is same for n = 23 * 57, 23 * 57, 313 * 477, so the actual primes doesn't matter but their exponents do, so you have to find all such numbers which contains all primes from 2 to largest prime factor in their factorisation. for example you have to consider n = 23 * 37 but not 23 * 57, because in second 5 is present but 3 is missing.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 Would you mind explaining how you calculate/estimate that there are around 2 * 106 such numbers? I think knowing how to do this estimation is crucial before one can decide to use this approach.
•  » » » 5 years ago, # ^ |   0 I used the code provided in spoiler.
 » 5 years ago, # |   0 Auto comment: topic has been updated by pabloskimg (previous revision, new revision, compare).
 » 5 years ago, # |   0 Auto comment: topic has been updated by pabloskimg (previous revision, new revision, compare).