Last Updated: 7 Jul, 2021
Sam and shopping
Hard
Asked in company
Sam goes to a shop having 'N' different items. The price of each of the items is 1 unit. He is a rich guy and has an infinite number of coins, each of value 'K' units. He wants to buy some things, but the total price of the items he buys must be multiple 'K'.
Find the number of ways in which he can buy some of the items from the shop.
You are required to print the answer modulo 100000.
Note:
Buying no item is also a valid way
For Example:
Input : N = 3, K = 2
Output : 4
Explanation:
There are 3 type of items; he can buy 2 items in 3 ways ({1,2}, {2,3} and {1,3}). and 0 items in 1 way, hence there will be a total of 4 ways.
Input Format:
The first line contains a single integer 'T' denoting the number of test cases to be run. Then the test cases follow.
The only line in the input contains two integers separated by a space, 'N' and 'K' denoting the number of items and the worth of one coin, respectively.
Output Format:
For each test case, print an integer denoting the number of ways to buy some of the items for each test case, as specified above.
Note :
You are not required to print anything; it has already been taken care of. Just implement the function.
Constraints:
1 <= T <= 50
1 <= N <= 10^12
1 <= K <= 10^3
Time Limit: 1 sec.
Approaches
In general, we have to compute the sum ∑ NC(M*K) modulo 100000 where M is from 0 to (N/K).
Here, the binomial coefficients can be taken from the polynomial coefficients as (1+x)^n.
We want to find the sum of the coefficients of x^i, where i is a multiple of K. We can take the powers modulo K here.
So, we can compute the coefficients of (1+x)^n using repeated squaring but only keep the first K coefficients. This will require O(log(n)) polynomial coefficients with, at most degree, K. We will use the efficient polynomial multiplication method FFT.
Algorithm
- Make function multiply: it will multiply two polynomials and return the result.
- Make function do_truncation it will use to truncate the polynomial into the optimal.
- Make function result to get the result for given n, k, and mod.
- Inside the result function, we will call the multiply function for a given input.
- Make two variables x and y.
- Call result for parameters n, k, and mod =2^5 and store it in x
- Call result for parameters n, k, and mod =5^5 and store it in y.
- Make variable ans = x*3125*29 +y*32*293
- Return the ans.