SPRNMBRS - Editorial

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 ext{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

12 Likes

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.

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

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

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

@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

1 Like

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

someone plz reply…

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

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

2 Likes

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

4 Likes

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



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 :frowning:

1 Like

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 :smiley:

Awesome question and till now found this as the best tutorial

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

1 Like

got the point…
thanks @shubhambhattar

@partyison you are welcome.

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

Uhm, the same one as mentioned in the editorial.