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

×

CDZ14D - Editorial

0
1

PROBLEM LINKS:

Practice
Contest

Author: sikander_nsit
Tester: sikander_nsit
Editorialist: sikander_nsit

DIFFICULTY:

MEDIUM

PROBLEM:

In this problem, we had to find the count of numbers between a range[R,L] such that their GCD with N is X.

EXPLANATION:

It would be the same as finding the count of numbers between L/X and R/X such that their GCD with N/X is 1. This is because if divide two numbers by their GCD then the resulting numbers would be coprime. So the task remains to find the count of numbers between a range which are coprime to N.

Let f(C) be the number of integers from 1 to A which are coprime to N.
So we can calculate our answer as f(R)-f(L-1). f(C) is A minus the number of integers that are not relatively prime to N. Call this number g(C). So f(C)=C−g(C). We attack the problem of finding g(C).

If N is a prime power p^a, it is easy.
The numbers in the interval [1,C] that are not relatively prime to N are the multiples of p.
Thus

g(C)=⌊C/p⌋

where ⌊x⌋ is the usual "floor" function.

If N has prime power factorization p^a*q^b, where p and q are distinct primes, then g(C) is the number of integers in [1,C] that are divisible by p or q or both. By Inclusion/Exclusion, we obtain

g(C)=⌊C/p⌋+⌊C/q⌋−⌊C/pq⌋.

The reason is that when we add the first two terms above, we are counting twice all the multiples of pq.

If N has prime power factorization p^a*q^b*r^c, the same basic idea works. We get

g(C)=⌊C/p⌋+⌊C/q⌋+⌊C/r⌋−⌊C/qr⌋−⌊C/pr⌋−⌊C/pq⌋+⌊C/pqr⌋.

The number of distinct primes for a number less than 10^9 will not be greater than 9. So bitmasking can be used to calculate all product combinations and then calculating f(R) and f(L-1). Each query can be answered in
O(2^number of distinct primes).

AUTHOR'S SOLUTION:

Author's solution can be found here.

This question is marked "community wiki".

asked 11 Feb '14, 04:20

sikander_nsit's gravatar image

5★sikander_nsit
1.5k82130
accept rate: 0%

edited 18 Apr '17, 22:05

admin's gravatar image

0★admin ♦♦
19.8k350498541


The questions should have been google proof.

link

answered 11 Feb '14, 17:32

sparshgunner12's gravatar image

4★sparshgunner12
1.1k51021
accept rate: 10%

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
×2,658
×639
×148
×10
×2

question asked: 11 Feb '14, 04:20

question was seen: 3,817 times

last updated: 18 Apr '17, 22:05