PROBLEM LINK:
Author: Kanstantsin Sokal
Tester: Jingbo Shang
Editorialist: Lalit Kundu
DIFFICULTY:
Easy-medium
PREREQUISITES:
number theory, euler totient
PROBLEM:
\phi(N) is defined as the number of positive integers less than or equal to N that are coprime with N. Let’s call a positive integer N a super number if N can be divided by \phi(N) without a remainder. You are given two positive integers L and R. Your task is to find count of super numbers in the range [L, R].
QUICK EXPLANATION:
======================
Note that \phi(N) = N*\frac{(p_1 - 1) * (p_2 - 1) * ... * (p_n - 1)}{p_1*p_2*...*p_n}. That means, (p_1 - 1) * (p_2 - 1) * ... * (p_n - 1) should divide p_1*p_2*...*p_n which is possible only when
- n=0
- n=1 and p_1=2
- n=2 and p_1=2 and p_2=3.
That is, count numbers of form N = 2^a * 3^b where a \gt 0 and b \ge 0 in range [L, R] which can be done in log_{2}{R}*log_{3}{R}.
Also don’t forget to count N = 1 if in range [L, R].
EXPLANATION:
================
You need to know about about two important properties of Euler’s Totient Function \phi(n).
- The function \phi(n) is multiplicative i.e. if \text{gcd}(m, n) = 1, then \phi(mn) = \phi(m) * \phi(n).
- Let’s see what is value of \phi(p^k) where p is a prime and k \ge 1. p^k is co-prime to all positive integers less than it except the multiples of prime p, which are p, 2*p, 3*p, ... p^{k-1}*p. Therefore, \phi(p^k) = p^k - p^{k-1}.
Using above two properties, we can define \phi(n) for a general N = p_1^{k_1}, p_2^{k_2}, ..., p_n^{k_n}(where p_i are distinct primes). We know, using multiplicative property that
\phi(N) = \phi(p_1^{k_1})*\phi(p_1^{k_1})* ...* \phi(p_n^{k_n})
which can be written as
\phi(N) = p_1^{k_1}*(1-\frac{1}{p_1})* p_2^{k_2}*(1-\frac{1}{p_2})* ... * p_n^{k_n}*(1-\frac{1}{p_n})
which is same as
\phi(N) = N*\frac{(p_1 - 1) * (p_2 - 1) * ... * (p_n - 1)}{p_1*p_2*...*p_n}.
Now, for \phi(N) to divide N, (p_1 - 1) * (p_2 - 1) * ... * (p_n - 1) should divide p_1*p_2*...*p_n. Let’s say we don’t include 2 as any of the p_i, then of course, its never possible because all primes p_i will be odd and p_i -1 is even for all primes.
So, we need to include p_1 = 2. So we want (p_2 - 1) * ... * (p_n - 1) to divide 2*p_2*...*p_n, where all p_2, p_3, ... p_n are odd. This can happen when
- n=0, i.e. N=1.
- n=1 and p_1=2, i.e N is a power of 2.
- n=2 and p_1=2 and p_2=3, i.e N is product of powers of 2 and 3.
Now, we just have to count numbers of this form in range L to R. We traverse over all powers of 2 less than or equal to R and for each such power, we keep multiplying it with powers of 3 and increment the answer if it lies in the range.
L, R = input
answer = 0
value = 2
while( value < = R )
current = value
while current <= R:
if L <= current <= R:
answer ++
current *= 3
value *= 2
//we haven't included N=1 in our answer
if L <= 1 <= R:
answer ++
print answer
COMPLEXITY:
================
There are log_{2}{R} powers of 2 we are considering and for each such power we can in worst case consider log_{3}{R} values. So, an upper bound on complexity can be said as log_{2}{R}*log_{3}{R}.
PROBLEMS TO SOLVE:
================
EXGCD
PUPPYGCD
