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 \leq n \leq 10^{13} \)
\( 1 \leq k \leq 10^4 \)

Please login to use the editor

You need to be logged in to access the code editor

Loading...

Please wait while we load the editor

Loading...
Results
Custom Input
Run your code to see the output
Submissions
Please login to view your submissions
Similar Problems
Points:50
3 votes
Tags:
AlgorithmsConvolutionFast Fourier transformMedium
Points:50
2 votes
Tags:
AlgorithmsApprovedFFTFast Fourier transformMedium