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

×

# PUPPYGCD - Editorial

Author: Pavel Sheftelevich
Editorialist: Pawel Kacprzak

HARD

# PREREQUISITES:

Math, Number-theory

# PROBLEM:

You are given integer N and integer D. Your task is to compute the number of unordered pairs of numbers $\{A, B\}$ such that $1 \leq A, B \leq N$ and $\gcd(A, B) = D$.

# QUICK EXPLANATION:

First notice that the number of pairs which we are looking for equals the number of co-prime number non-greater than $N \mathbin{/} D$. Then use Euler-totient function to compute the number of co-prime numbers not-greater than $N \mathbin{/} D$. In order to pass all testcase, use precomputation of sums of Euler-totient function for some intervals to speed up the real time computation.

# EXPLANATION:

The crucial observation here is that the number of unordered pairs of number $\{A, B\}$ not greater than $N$, for which $\gcd(A, B) = D$ equals the number of co-prime numbers not greater than $N \mathbin{/} D$. This is true, because if you multiply these co-prime numbers by $D$, then their $\gcd$ equals $D$, since they do not share any common prime factors other that prime factors of $D$.

We just reduced our problem to finding the number of co-prime number non greater than some integer $N$.

The most straightforward method to do that is to iterate over all possible pairs of number and check if their $\gcd$ equals $1$ using Euclid algorithm. This results in algorithm which has $O(N^2 \cdot \log(N))$ complexity. This allows us to solve the first subtasks, but is a way too slow for higher constraints.

The faster solution uses Euler-totient function which is a very famous function denoted by $\phi(N)$. The value of $\phi(N)$ is the number of positive integers not greater than $N$ which are co-prime with $n$. It can be computed using factorization. So the number of co-prime number smaller than $N$ equals the sum of $\phi(i)$ for all $i \leq N$. For more details, I encourage you to read this great topcoder tutorial on prime numbers, factorization and Euler function. But since we have to compute $\phi(i)$ for all numbers from $1$ to $N$, this will time out, because $N$ can be at most $5 * 10^8$.

In order to speed up our solution, we can precompute values of sums of $\phi$ of integers not greater than $K, 2 K, 3K, \dots, N - K$ for reasonable chosen $K$. Author of the problem decides to choose $K$ to be $250000$. This allows us to compute $\phi$ for at most $K$ different values and uses the precomputed sum of $\phi$ for smaller values.

The time complexity here depends on $K$ and equals $O(K \cdot \log(N) + N \cdot \log(\log(N)))$, where the first summand is taken from computing $\phi$ for at most $K$ values, and the second is taken from computing prime numbers using in factorization - we can use the sieve in order to do that.

# AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.
Tester's solution can be found here.

This question is marked "community wiki".

asked 26 Jul '15, 14:27 19.8k350498541
accept rate: 36%

I am not able to understand why there is a term of k.log(n) in the time complexity. According to author and tester solutions, these k values are calculated from a different code. Also how can we compute the sum of all k values up to N in time K.log(n).

(28 Jul '15, 11:56) 4★

 15 Basically this question requires you to efficiently compute the sum of etf form 1 to n/d For doing same an awesome post by a user mclo is here !  Implementation of above -> Solution link answered 26 Jul '15, 14:54 6★adkroxx 306●7●19 accept rate: 7% How can your code pass in given time if n=5*10^8 and d = 2 as in you code this for loop :"for(val=n/d; val>0; val--){}" iterate n/d times? (26 Jul '15, 16:08) For that function d isn't that one given in problem ... For the loop which you are talking about d has reached around sqrt(n) at that time ! So you need to iterate sqrt(n) times ! (26 Jul '15, 17:19) adkroxx6★ Can you please explain your code a little bit? I understood the part where you found the ETF function and their summation. This is enough for two subtasks. But how did you find the results when the number is more than MAX? Please give some hints. (27 Jul '15, 20:05) 3 I make use of the recursion shown in the picture ! (WARNING: d in that function isn't that one given in problem) Idea is (n/d) value will be unique for d less than or equal to sqrt(n) .. After that (n/d) will assume only sqrt(n) different values .. that is (n/d) would repeat for ranges of d ! So instead of iterating d from sqrt(n) to n directly .. you can just iterate (n/d) itself and corresponding to that obtain the range of d ! Simmilar problem with this idea: 1. spoj.com/problems/AFS2 2. https://projecteuler.net/problem=401 (28 Jul '15, 01:07) adkroxx6★ nice implementation. easy to understand as well. (22 Jul '16, 21:14) likecs6★
 2 @ayushtomar @ironmandhruv : Apologies, the solution links have been fixed. answered 26 Jul '15, 15:06 0★admin ♦♦ 19.8k●350●498●541 accept rate: 36%
 2 Basically , what i got is we have to find summation of ETF from 1 to p where p is n/d . But the actual problem was how to do that summation . Thanks adkroxx for the solution implementation . answered 26 Jul '15, 15:09 71●4 accept rate: 0%
 0 Neither author nor tester's solution are available answered 26 Jul '15, 14:41 141●1●5 accept rate: 4%
 0 @adkroxx where did you find this nice piece of theory? answered 26 Jul '15, 15:57 4★k0stia 41●6 accept rate: 0% Problems on projecteuler.net have thread forum associated with them and also overview for many of them once you solve a problem .. Above theory is one of them :-) (26 Jul '15, 20:36) adkroxx6★
 0 @adkroxx ,i didnt get this,,,if n(n+1)/2= |{1<=a<=b<=n}|=\sum(phi(n/d)) ,then how required_ans=n(n+1)/2-\sum(phi(n/d)),,,(sorry i didnt know how to use latex here) answered 26 Jul '15, 20:37 16●1 accept rate: 14% (n*(n+1))/2 = sum(sp(n/d)) (d=1 to n) i.e. (n*(n+1))/2 = sp(n/1) + sum(sp(n/d)) (d=2 to n) rearrange to get answer .. here sp is summation of phi function ! (26 Jul '15, 20:42) adkroxx6★ got it thnx,so silly of me (26 Jul '15, 23:56)
 0 Nice problem. Learned a very good thing. Thanks. answered 27 Jul '15, 10:24 893●2●11●35 accept rate: 10%
 toggle preview community wiki:
Preview

### Follow this question

By Email:

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

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,852
×890
×639
×41

question asked: 26 Jul '15, 14:27

question was seen: 7,579 times

last updated: 22 Jul '16, 21:14