×

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

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★

 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

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

question asked: 26 Jul '15, 14:27

question was seen: 7,579 times

last updated: 22 Jul '16, 21:14