DMOPC '15 Contest 1 P4 - Itami and Candy

View as PDF
Submit solution
Points: 10 (partial)
Time limit: 0.6s
Memory limit: 64M
Authors:
Xyene, FatalEagle
Problem type

Itami has bought 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, her favorite number, and Tuka, trying to keep a slim and trim figure, will take at most 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 candies; he can choose to eat any remainders by himself.

Note

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

Input Specification

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

Output Specification

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

Sample Input 1

3 1

Sample Output 1

4

Explanation for Sample Output 1

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

Sample Input 2

1 1

Sample Output 2

0

Explanation for Sample Output 2

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

Sample Input 3

10 3

Sample Output 3

19

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.

    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.

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