In this [problem:615D] after analyzing some cases, I saw that,↵
↵
If a number n = p1^a * p2^b * p3^c.↵
↵
Then for the answer, the contribution of each prime is something like -↵
↵
Let that , calculating the contribution of p1 --->↵
↵
~~~~~↵
x = (a * (a+1) )/2;↵
y = (b+1)*(c+1) [ That is , how many divisors are there without the prime p1]↵
↵
z = x*y↵
so the contribution of p1 is p1^z↵
~~~~~↵
↵
↵
To calculate y , I had to use two loops.↵
And got TLE[submission:https://codeforces.com/contest/615/submission/86303876]. How to optimize this portion?↵
↵
If a number n = p1^a * p2^b * p3^c.↵
↵
Then for the answer, the contribution of each prime is something like -↵
↵
Let that , calculating the contribution of p1 --->↵
↵
~~~~~↵
x = (a * (a+1) )/2;↵
y = (b+1)*(c+1) [ That is , how many divisors are there without the prime p1]↵
↵
z = x*y↵
so the contribution of p1 is p1^z↵
~~~~~↵
↵
↵
To calculate y , I had to use two loops.↵
And got TLE[submission:
