(Codeforce 757) E. Bash Plays with Functions

Title:

Sample input:

50 301 253 652 54 48

Sample output:

85254630

Title:

Let's analyze the situation of r=0 first, if we now find f0(n), n=p1^a1*p2^a2*...*pm^am

Then f0(n) is equal to 2^m, which is obvious, because we assume p=p1^b1*p2^b2*...*pm^bm, then for any bi (1<=i<=m) all have bi=0 or bi=ai, otherwise there will be no q such that p*q=n and gcd(p,q)=1, then it is not difficult for us to find that f0(x) is an integralfunction.Assuming that for n=p*q, gcd(p,q)=1, there will be no identical prime factors in the prime factorization of p and q. It may be assumed that p has i prime factors and q has j prime factors, thenp*q will have i+j prime factors, then f0(pq)=2^(i+j)=2^i*2^j=f0(p)*f0(q), so f0(x)is an integral function.

Below I use induction to prove that for any r, fr(x) is an integral function.

We know that for the case of r=0, the value of f0(n) is only related to the type of prime factor of n, not the specific prime factor.The case where r is not 0 is obtained from the case where r=0, so when r is not 0, it has nothing to do with the specific prime factor.We deduced above that fr(x) is an integral function for any r, so we only need to look at the prime factorization of n when we find fr(n), then the problem becomes to solve fr(p^i), p is a prime number, according to the formula we can find fr(p^i)=, and because it has nothing to do with the specific prime factor, through the above formula we can find that it is only related to the number of prime factors, thenWe can let f[i][j] record the value of fi(p^j), since n is less than 1e6, so the highest number of prime factorization will not exceed 20, so that all numbers can be preprocessed through O(r*20).When r=0, according to its definition we can know that f[0][1]=1,f[0][i]=2(i>1), preprocess it

The rest is to record the number of prime factors for each group of queries, and directly use the property of the integral function to solve it.

Here is the code:

#include#include#include#include#include