PUPPYGCD - Editorial

PROBLEM LINK:

Practice
Contest

Author: Pavel Sheftelevich
Tester: Vlad Mosko
Editorialist: Pawel Kacprzak

DIFFICULTY:

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.

2 Likes

Neither author nor tester’s solution are available

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 !

alt text

alt text

Implementation of above -> Solution link

15 Likes

@ayushtomar @ironmandhruv : Apologies, the solution links have been fixed.

2 Likes

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 .

2 Likes

@adkroxx where did you find this nice piece of theory?

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

Nice problem. Learned a very good thing. Thanks.

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?

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 !

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

(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 !

got it thnx,so silly of me

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.

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
2 Likes

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

nice implementation. easy to understand as well.