PROBLEM LINK:Author: Kanstantsin Sokal DIFFICULTY:Easymedium 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:======================
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:================
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) = 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})$ 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
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.
COMPLEXITY:================ PROBLEMS TO SOLVE:================ AUTHOR'S, TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 19 Sep '15, 18:06

I solved this problem simply by printing the first few numbers and seeing the pattern :D answered 22 Sep '15, 16:21
@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)

@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
got the point.. thanks @shubhambhattar
(22 Sep '15, 00:36)
@partyison you are welcome.
(22 Sep '15, 01:21)

@shubhambhattar You are wrong because of precision(you use pow function). Here is the difference 
Final answers  powWay = 33354363399333136 mulWay = 33354363399333138 answered 21 Sep '15, 13:30

@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

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

@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

very good explanation...........given by Editorialist.... I want to say wow here is my code..
} SHAME ON ME COULD NOT COMPLETE IN LIVE CONTEST* HAPPY CODING answered 21 Sep '15, 01:28

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

@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

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

Awesome question and till now found this as the best tutorial answered 19 Feb '17, 17:39

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