MHB How to Efficiently Compute Euler's Totient Function for Large Ranges?

[Saitama]

Following is the problem I am trying to solve: SPOJ.com - Problem ETFS

In number theory, the totient phi(n) of a positive integer n is defined to be the number of positive integers less than or equal to n that are coprime to n.

Input

The lonely line in input contains two integers a, b.

Output

Print phi(n) for n from a to b (inclusive).

Example

Input:
1 5

Output:
1
1
2
2
4

Constraints

0 < a < b < 10^14
b - a < 10^5

Here is my code:

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

typedef long long ll;

ll solve(ll n)
{
	ll i, ans=n;
	for(i=2; i*i<=n; ++i)
	{
		if(n%i==0)
			ans-=ans/i;
		while(n%i==0)
			n/=i;
	}
	if(n>1)
		ans-=ans/n;
	return ans;
}

int main() {
	ll T, n, a, b, i;
	scanf("%lld %lld", &a, &b);
	vector<ll> x(b-a+1, -1);
	for(n=a; n<=b; ++n)
	{
		if(x[n-a]==-1)
		{
			x[n-a]=solve(n);
			if(2*n<=b)
			{
				if(n%2) x[2*n-a]=x[n-a];
				else x[2*n-a]=2*x[n-a];
			}
			for(i=n*4; i<=b; i*=2)
			{
				x[i-a]=2*x[i/2-a];
			}
		}
	}
	for(i=0; i<b-a+1; ++i)
		printf("%lld\n", x[i]);
	return 0;
}

Some explanation of what I am trying to do.

The naive approach i.e finding $\phi (n)$ of every number in the given range using the $O(\sqrt{n})$ won't work. So whenever I have found $\phi(n)$, I use the following relation: $\phi(2n)=2\phi(n)$ if $n$ is even and $\phi(2n)=\phi(n)$ is $n$ is odd. With this, I don't have to run the solve() function ($O(\sqrt{n}$) for every integer in the range but even with this optimisation, I get TLE. :(

Please help. Thanks!

 

[I like Serena]

Hi Pranav,

Perhaps we can use that
\begin{cases}\phi(p)&=p-1\\\phi(p^n)&=(p-1)p^{n-1}\\\phi(a\cdot p^n)&=\phi(a)\cdot\phi(p^n) &\text{ if }p\nmid a\end{cases}
Then we might apply a sieve or dynamic programming.

 

[Nono713]

Hint: trial division is not the only factorization algorithm that exists. There are many more advanced algorithms, some of which are easy to implement and will pretty much instantly factor your input integers up to 10^14. For instance, Pollard's Rho is pretty simple to implement, and in practice runs in worst case $O(\sqrt[4]{n})$.

Then you can use I Like Serena's suggestions to take advantage of the fact that you have to factor a range of consecutive integers, etc...