Help...Prime multiples CSES

help
1

hello,what can be best approach to solve the Prime Multiples problem in CSES problem set.
problem link:https://cses.fi/problemset/task/2185/;
my code: https://cses.fi/paste/045e5e1886f8c77f19af18/
my code is working for only one test case…plz help.

2
  1. You do know gcd of two primes is always 1, so lcm= prime1 * prime2 :slight_smile:
  2. Use the general inclusion-exclusion principle since pairs aren’t the only ones involved.
1 Like
3

Problem
Count the numbers that are divisible by at least 1 prime in set A.

Your approach

  1. Count numbers that are divisible by each prime individually
  2. Subtract numbers that are divisible by each pair of primes

Problem with your approach
It’s not how inclusion exclusion works. Refer here.

Let me explain with a simple example. Consider 3 primes 3, 5 ,7
Denote 3 sets X_1, X_2, X_3 as follows

  • X1= all numbers divisible by only one of 3,5,7. (example, 3, 9, 14)
  • X2= all numbers divisible by exactly two of 3,5,7. (example 70, 15)
  • X3= all numbers divisible by exactly three of 3,5,7 (example 210)

Note that these 3 sets are disjoint and don’t intersect. What you need to find is sum of their sizes.
Now let’s look at your approach

In first step, you count X1 exactly once, X2 exactly twice and X3 exactly thrice
So for instance,9 is counted once, 35 is counted twice and 210 is counted thrice
In second step, you count X2 exactly once, and X3 thrice
For instance, 9 is not counted, 35 is counted once, and 210 is counted thrice.

Now you are subtracting the two, you are only getting one copy of X1 and X2. You need to add X3 back.

This is the basic idea of inclusion exclusion principle.

K=20 means you can use inclusion exclusion by iterating over all 2^20 subsets of what numbers are selected and what are not. (if even numbers are selected, you subtract from result, if odd are selected, you add to result)

Maybe there is a better solution but I don’t see it right now.

3 Likes
4

Instead of using two for loop use segmented sieve of Eratosthenes algo(the value of n 10^18 is ) to find the number of prime in range

hope this will help u

1 Like
5

@cubercoder
I have worked exactly same but my answer differ with original answer. Why???
My Code: https://cses.fi/paste/6e8107a6a3d1b3f71c4d63/

6

when You did prod*=prime[j] in the second ‘for’ loop then prod goes out of range of ‘long’ and for that reason your codes shows wrong output for some test cases.

7

Read This it will help you in Solving this Problem…
link: The Inclusion-Exclusion Principle - Algorithms for Competitive Programming
It Helped me too.
And just take care of large product value…
I have use double instead of long long

You can Read Below after checking Above Link, then you can understand where Problem actually occurs.
double mult = 1
mult *= a[i]
ans = n/(long long)mult

4 Likes