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

UPDATE 1: why the downvotes?

UPDATE 2: based on the answers so far, the solution would be to exhaustively explore all combinations of exponents *k*_{1}, *k*_{2}, ..., *k*_{r} (*k*_{i} ≥ *k*_{j} for all *i* < *j*) such that and *k* = 2^{k1} * 3^{k2} * 5^{k3} * 7^{k4} * 11^{k5} * ... < 2^{63}. 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 * 10^{6} valid combinations of exponents, where did he get that number from?

Let the prime factorisation of

nbep_{1}^{n1}p_{2}^{n2}....p_{k}^{nk}, then we have , which means that f(n) doesn't depend on primes but instead on the exponents. So you can find all numbers ( < 2^{63})which are formed by first few primes, Mathematically , you have to find all such numbers such that if the prime factorisation ofncontains primep, then it must contains all primes less thanp. The number of such numbers is around 2 * 10^{6}, so you preprocessf(n) for all thosenand get the answer for all givenninO(1). My code for finding such numbers is in spolilerSpoiler"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?

The value of

f(n) is same forn= 2^{3}* 5^{7}, 2^{3}* 5^{7}, 31^{3}* 47^{7}, 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 considern= 2^{3}* 3^{7}but not 2^{3}* 5^{7}, because in second 5 is present but 3 is missing.Would you mind explaining how you calculate/estimate that there are around 2 * 10

^{6}such numbers? I think knowing how to do this estimation is crucial before one can decide to use this approach.I used the code provided in spoiler.

Auto comment: topic has been updated by pabloskimg (previous revision, new revision, compare).Auto comment: topic has been updated by pabloskimg (previous revision, new revision, compare).