### PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

**Setter:** Himanshu Mishra

**Tester:** Alexey Zayakin and Yash Chandnani

**Editorialist:** Taranpreet Singh

### DIFFICULTY:

Cakewalk.

### PREREQUISITES:

Greatest Common Factor and Least Common Multiple.

### PROBLEM:

Given four numbers N, A, B and K. There are N problems labelled from 1 to N. Appy solves each problem whose label is divisible by A but not B, while Chef solves all problems whose label is divisible by B but not by A. Check if Appy and Chef together solve at least K problems or not.

### QUICK EXPLANATION

- Number of problems solved by Appy is N/A - N/lcm(A, B).
- Number of problems solved by Chef is N/B - N/lcm(A,B).
- Total number of problems solved become N/A+N/B-2*N/lcm(A,B). We can simply check if it is at least K or not.

### EXPLANATION

Number of multiples of x in range [1, N] is given by \lfloor N/x \rfloor.

Appy solves all problems whose label is divisible by A, which are N/A problems. But this also includes problems whose labels are divisible by both A and B. We know, all such problems are the multiples of lcm(A, B). So, we can just subtract it from N/A to get N/A - N/lcm(A, B) which is the number of problems solved by Appy.

Chef solves all problems whose label is divisible by B, which are N/B problems. But this also includes problems whose labels are divisible by both A and B. We know, all such problems are the multiples of lcm(A, B). So, we can just subtract it from N/B to get N/B - N/lcm(A, B) which is the number of problems solved by Chef.

The total number of problems solved by Chef and Appy is N/A+N/B-2*N/lcm(A, B). We can simply use an if statement to check if this exceeds K or not.

As an exercise, solve the problem, where problems are not labeled from 1 to N, but from L to R which is given in the problem.

Finding LCM of two numbers is just the product of two numbers divided by its Greatest Common Factor, which can be easily found using Euclid’s GCD method.

### Time Complexity

Time complexity is O(1) per test case.

### AUTHOR’S AND TESTER’S SOLUTIONS:

Setter’s solution

Tester’s solution

Editorialist’s solution

Feel free to Share your approach, If it differs. Suggestions are always welcomed.