×

SPRNMBRS - Editorial

Author: Kanstantsin Sokal
Tester: Jingbo Shang
Editorialist: Lalit Kundu

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

value = 2
while( value < = R )
current = value
while current <= R:
if L <= current <= R:
current *= 3
value *= 2

//we haven't included N=1 in our answer
if L <= 1 <= R:



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}$.

================
EXGCD
PUPPYGCD

AUTHOR'S, TESTER'S SOLUTIONS:

This question is marked "community wiki".

3.0k93164187
accept rate: 12%

19.8k350498541

1

I am getting an "Access Denied" error when I try to view the "Setter" and "Tester" solutions.

(21 Sep '15, 00:05)

 4 I solved this problem simply by printing the first few numbers and seeing the pattern :D answered 22 Sep '15, 16:21 7★xellos0 5.9k●5●42●92 accept rate: 10% @xellos0 Can u please tell what kind of pattern have u observed? (23 Sep '15, 00:12) Uhm, the same one as mentioned in the editorial. (23 Sep '15, 00:33) xellos07★
 2 @partyison Let's try with other prime numbers for the following expresion: $\frac{p_{1}p_{2}p_{3}....p_{n}}{(p_{1}-1)(p_{2}-1)(p_{3}-1)....(p_{n}-1)}$ I hope you got the point why 2 is included, that's because if $p_{1} = 2$, then $(p_{1}-1) = 1$ and then $\frac{p_{1}}{p_{1}-1}$ is an integer, thus we can include $2$. After this, we try to do this for increasing values of $n$ taking into account the sequence of prime numbers. Let $n = 2, p_{1} = 2, p_{2} = 3$, then $\frac{p_{1}p_{2}}{(p_{1}-1)(p_{2}-1)} = \frac{2.3}{1.2} = 3$ which is still an integer, so this is acceptable. Let $n = 3, p_{3} = 5$, then $\frac{p_{1}p_{2}p_{3}}{(p_{1}-1)(p_{2}-1)(p_{3}-1)} = \frac{2.3.5}{1.2.4} = \frac{15}{4}$ which is not an integer, so not acceptable. Let $n = 4, p_{4} = 7$, then $\frac{p_{1}p_{2}p_{3}p_{4}}{(p_{1}-1)(p_{2}-1)(p_{3}-1)(p_{4}-1)} = \frac{2.3.5.7}{1.2.4.6} = \frac{35}{8}$ which is not an integer, so not acceptable. You can try more combinations for different values of $n$ but I think you get the idea. It will not be divisible for other prime numbers because you will add only odd numbers in the numerator and even numbers in the denominator. Some more points to note is that it is not necessary to include both $2$ and $3$ for every $N$ in the given range. That's why the general expression for $N$ in the editorial is given as $N = 2^{a}3^{b}$ where $a > 0 \ and \ b \geqslant 0$. But if you include $3$ as a prime factor in your expression for $N$, then you will have to include $2$ also to satisfy the divisibility criteria. Also, $1$ trivially satisfies the criteria, thus it's also included. answered 22 Sep '15, 00:07 288●9 accept rate: 23% got the point.. thanks @shubhambhattar (22 Sep '15, 00:36) @partyison you are welcome. (22 Sep '15, 01:21)
 1 @shubhambhattar You are wrong because of precision(you use pow function). Here is the difference -  //Calculate 2*3^34 in 2 different way long long powWay; //Calculate using power powWay = pow(2, 1) * pow(3, 34); long long mulWay = 2; //Calculate using multiplication for(int i = 0; i < 34; ++i) mulWay *= 3;  Final answers - powWay = 33354363399333136 mulWay = 33354363399333138 answered 21 Sep '15, 13:30 4★konfused 21●1 accept rate: 0%
 1 @shubhambhattar I checked your WA solution & found that your prepossessed vector misses these 2 numbers - (3 * 2^58) & (3^3 * 2^55). When I drill down to find why, I found this weird behavior on GCC. Check the following 2 codes give different output. http://ideone.com/ObyWf7 http://ideone.com/wiv9ya These code give same output (1 as expected) on VS2012. I do not use linux much so I cant debug further. I tried to put this as question on codechef but it didn't allow me - (no Karma). Let me know if you can find reason for this. Putting this in another answer as I can't find how to comment on other's (your) answer as partyison did above :( answered 22 Sep '15, 19:24 4★konfused 21●1 accept rate: 0%
 0 I am getting wrong answer for my solution. Can somebody point out my mistake? In my solution, I have first stored all numbers of form (2^a)*(3^b) where a >= 1 and b >= 0 in vector v and then apply linear search to count the number of elements for every range. answered 21 Sep '15, 00:20 288●9 accept rate: 23%
 0 @shubhambhattar, a>=0 and b>=0 as per the conditions provided by you. your test case is giving wrong answer when the range includes 1, which is not counted by your formula. By definition, phi(1) = 1, meaning 1%phi(1) = 0. For more help, see the editorial pseudo code. answered 21 Sep '15, 00:45 6★likecs 3.7k●23●80 accept rate: 9%
 0 @likecs I have also made a submission in which 1 is included, that's here. That too gave me a wrong answer. And the constraints should be a > 0 (or a >= 1) not a >= 0. answered 21 Sep '15, 01:14 288●9 accept rate: 23%
 0 very good explanation...........given by Editorialist.... I want to say wow here is my code..  /* Ramesh Chandra O(logL*logR) */ #include using namespace std; int main(){ int T; cin >> T; while(T--){ long long int L,R; cin >> L >> R; long long int ans=0; //here 1 is also super number...... if( L<=1 && R>=1) ans++; //after a long time after looking into tutorial //you need to calculate only number in range //that can we made using only 2 * 3 .. //here 3 can be absent but not 2 long long int value2=2; while(value2<=R){ long long int value3=value2; while(value3<=R){ if(value3>=L) ans++; value3*=3; } value2*=2; } cout<
 0 can somebody explain why n is only upto 2?and why you used 2 and 3 only,what about other prime factors n=0, i.e. N=1. n=1 and p1=2, i.e N is a power of 2. n=2 and p1=2 and p2=3, i.e N is product of powers of 2 and 3.  i am a newbie.please help answered 21 Sep '15, 15:45 1 accept rate: 0%
 0 someone plz reply... answered 21 Sep '15, 19:40 1 accept rate: 0%
 0 @konfused I removed the power function and placed a loop to do the same but still got wrong answer. Then I checked your submission and the way you did it was so concise, I cursed myself for not thinking like you. I changed my code and it worked. Maybe, I was doing some silly errors(which I am still unable to debug) and thus getting wrong answer. Here's my submission if you want to take a look. And thanks for the help. answered 21 Sep '15, 23:25 288●9 accept rate: 23%
 0 I tried this question in simple way , but it is showing wrong answer . Can anyone please tell my mistake? http://ideone.com/szahS8 , this the link of my code. Thanks in advance :D answered 22 Sep '15, 21:31 1 accept rate: 0%
 0 Awesome question and till now found this as the best tutorial answered 19 Feb '17, 17:39 7●1●3 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,680
×1,672
×631
×52
×16

question asked: 19 Sep '15, 18:06

question was seen: 5,063 times

last updated: 19 Feb '17, 17:39