DMOPC '15 Contest 1 P4 - Itami and Candy - Olympiads Online Judge

DMOPC '15 Contest 1 P4 - Itami and Candy

Points: 10 (partial)

Time limit: 0.6s

Memory limit: 64M

Authors:

Problem type

Itami has bought $N$ $N$ pieces of candy, and would like to share them with his friends.

However, they are very picky about the amount of candies that they eat. Lelei only wants a prime number of candies, Rory wants candies in multiples of $X$ $X$ , her favorite number, and Tuka, trying to keep a slim and trim figure, will take at most $1$ $1$ candy.

In how many different ways can Itami distribute his bag of candies? A distribution is considered different if at least one of his friends gets a different amount of candy. Note that Itami does not have to distribute all $N$ $N$ candies; he can choose to eat any remainders by himself.

Note

A prime number is a positive integer greater than $1$ $1$ that has no other factors other than $1$ $1$ and itself.
A multiple of a number $X$ $X$ is any number $Y$ $Y$ such that $\dfrac{Y}{X}$ $\frac{Y}{X}$ is an integer.

Input Specification

The first line of input will contain two space-separated integers $N$ $N$ $(1 \le N \le 148\,734)$ $(1 \leq N \leq 148 734)$ , the number of candies Itami has, and $X$ $X$ $(1 \le X \le N)$ $(1 \leq X \leq N)$ , Rory's favorite number.

Output Specification

A single integer, the number of ways Itami can hand out his candies.

Sample Input 1

Copy

3 1

Sample Output 1

Copy

Explanation for Sample Output 1

The ways of distributing are, in order of $\{\textrm{Lelei, Rory, Tuka}\}$ ${Lelei, Rory, Tuka}$ : $\{2, 0, 0\}$ ${2, 0, 0}$ , $\{2, 0, 1\}$ ${2, 0, 1}$ , $\{2, 1, 0\}$ ${2, 1, 0}$ , $\{3, 0, 0\}$ ${3, 0, 0}$ .

Sample Input 2

Copy

1 1

Sample Output 2

Copy

Explanation for Sample Output 2

Lelei must take at least $2$ $2$ candies, but Itami doesn't have that many to give. Thus, there is no way to distribute candies.

Sample Input 3

Copy

10 3

Sample Output 3

Copy

Comments

1

alexker commented on Feb. 27, 2016, 11:19 p.m.

Hi All,

I have tested my code with all the test cases and it seems to be working fine. However, it is very inconsistent within the batches.It would be great if someone can offer a hint.

Thanks!

3

aurpine commented on Feb. 28, 2016, 1:52 a.m.

I think you forgot to take into consideration the case where there is not enough candy left to give to Tuka.

-1

alexker commented on Feb. 28, 2016, 3:57 a.m. ← edited →

I included the two cases: one Tuka takes one candy, and the other one he does not. Are you sure that is the problem? Thanks!

-1

bobhob314 commented on Oct. 13, 2015, 11:55 p.m.

Multiples can't be negative right?

1

FatalEagle commented on Oct. 14, 2015, 12:32 a.m.

Each person must get zero or more candies.

-6

MathBunny commented on Oct. 13, 2015, 10:14 p.m.

Why can't you eat no candies?

This comment is hidden due to too much negative feedback. Show it anyway.

2

FatalEagle commented on Oct. 13, 2015, 11:00 p.m.

No comment. Read the task description again.

-5

MathBunny commented on Oct. 14, 2015, 9:04 p.m.

Lol I was stupid ignore me

This comment is hidden due to too much negative feedback. Show it anyway.