Ash and shopping
Practice
3.8 (11 votes)
Divide And Conquer algorithm
Fast fourier transform
Generating functions
Medium
Problem
12% Success 1524 Attempts 50 Points 4s Time Limit 256MB Memory 1024 KB Max Code

Ash goes to a shop which has n different items. The price of each of the items is 1 unit . Ash is a rich guy and has infinite coins each of value k units. Now he wants to buy some of the items, but he wants to make sure that he can pay for all the items he buys using the coins he has. Formally, the total price of the items he buys must be a multiple of k.
Find the number of ways in which he can buy some of the items from the shop. Since this number can be pretty huge, print only last 5 digits of the answer.
Two ways are considered distinct if there exists an i, such that item i is bought in only one of them. Buying no item is also a valid way.

Input:
The only line in the input contains two integers separated by a space, n and k.

Output:
Print the last 5 digits of the number of ways in which he can buy some of the items, as specified above.

Constraints:
1≤n≤1013
1≤k≤104

Sample Input
3 2
Sample Output
4
Explanation

Ash can buy either 0 items in 1 way or 2 items in 3 ways. So, the total number of ways is 4

Code Editor

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Submissions
Please login to view your submissions
Similar Problems
Points:50
2 votes
Tags:
AlgorithmsApprovedFFTFast Fourier transformMedium
Points:50
3 votes
Tags:
AlgorithmsConvolutionFast Fourier transformMedium
Editorial

Login to unlock the editorial