You are not logged in. Please login at www.codechef.com to post your questions!

×

SPRNMBRS - Editorial

13
4

PROBLEM LINK:

Practice
Contest

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

AUTHOR'S, TESTER'S SOLUTIONS:

setter
tester

This question is marked "community wiki".

asked 19 Sep '15, 18:06

darkshadows's gravatar image

5★darkshadows ♦
3.0k93164187
accept rate: 12%

edited 21 Sep '15, 00:04

admin's gravatar image

0★admin ♦♦
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) noble_mushtak5★

I solved this problem simply by printing the first few numbers and seeing the pattern :D

link

answered 22 Sep '15, 16:21

xellos0's gravatar image

7★xellos0
5.9k54393
accept rate: 10%

@xellos0 Can u please tell what kind of pattern have u observed?

(23 Sep '15, 00:12) shiva_google2★

Uhm, the same one as mentioned in the editorial.

(23 Sep '15, 00:33) xellos07★

@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.

link

answered 22 Sep '15, 00:07

shubhambhattar's gravatar image

3★shubhambhattar
2889
accept rate: 23%

got the point.. thanks @shubhambhattar

(22 Sep '15, 00:36) partyison2★

@partyison you are welcome.

(22 Sep '15, 01:21) shubhambhattar3★

@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

link

answered 21 Sep '15, 13:30

konfused's gravatar image

4★konfused
211
accept rate: 0%

@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 :(

link

answered 22 Sep '15, 19:24

konfused's gravatar image

4★konfused
211
accept rate: 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.

link

answered 21 Sep '15, 00:20

shubhambhattar's gravatar image

3★shubhambhattar
2889
accept rate: 23%

@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.

link

answered 21 Sep '15, 00:45

likecs's gravatar image

6★likecs
3.7k2481
accept rate: 9%

@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.

link

answered 21 Sep '15, 01:14

shubhambhattar's gravatar image

3★shubhambhattar
2889
accept rate: 23%

very good explanation...........given by Editorialist.... I want to say wow

here is my code..


 /*

       Ramesh Chandra
       O(logL*logR)
 */

  #include<bits/stdc++.h>
  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<<ans<<endl;
   }

return 0;

}


SHAME ON ME COULD NOT COMPLETE IN LIVE CONTEST*

HAPPY CODING

link

answered 21 Sep '15, 01:28

rcsldav2017's gravatar image

5★rcsldav2017
1.1k1229
accept rate: 6%

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

link

answered 21 Sep '15, 15:45

partyison's gravatar image

2★partyison
1
accept rate: 0%

edited 21 Sep '15, 15:50

someone plz reply...

link

answered 21 Sep '15, 19:40

partyison's gravatar image

2★partyison
1
accept rate: 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.

link

answered 21 Sep '15, 23:25

shubhambhattar's gravatar image

3★shubhambhattar
2889
accept rate: 23%

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

link

answered 22 Sep '15, 21:31

parul_bansal's gravatar image

2★parul_bansal
1
accept rate: 0%

Awesome question and till now found this as the best tutorial

link

answered 19 Feb '17, 17:39

mayank1995's gravatar image

1★mayank1995
713
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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,852
×1,722
×639
×52
×16

question asked: 19 Sep '15, 18:06

question was seen: 5,083 times

last updated: 19 Feb '17, 17:39