DCP-125: One Math to Save Them All Back to All Problems

Medium Math > Combinations and Permutations


In the land of Middle Earth, there lived a frightening “mathological” creature. It asked people a hard math problem and if people were not able to answer correctly, they were eaten alive. It asked people the following math problem: Count the number of ways to distribute **N** unique items to **M** people so that each people gets same number ( **N/M** ) of items where N is **multiple** of M. Giving the solution modulo some huge prime number was enough to survive. With the passage of time the fear of the creature declined. People were easily be able to answer the question. So the creature decided to adapt, he started asking the number of digits of the solution. The people were faced with a new threat as they were not able to answer the question. So they came to you, the famous “Mathrandir”. Can you answer the questions and save all the people? Input: ------ First line gives number of test cases (T). T lines follow, each containing N and M. Output: ------- For each test case print the number of digits of the actual solution to the problem. Limits: ------- T<=10000 M<=N<=100000 N is multiple of M Sample Input ------------ 2 4 4 10 5 Sample Output ------------- 2 6 Explanation ------------ There are 24 ways to distribute 4 items among 4 people. So number of digits is 2. Similarly, there are 113400 ways in second test case. So answer is 6.


Problem Setter:

Sheikh Moinul Hasan

Please login to submit solution to this problem.

Problem Limits

Language Time Limit (seconds)
C 2.00
C++ 2.00
C++14 2.00
C# 4.00
Go 4.00
Java 4.00
JavaScript 4.00
Objective-C 4.00
Perl 4.00
PHP 4.00
Python 4.00
Python3 4.00
Ruby 4.00
VB.Net 4.00

Problem Stats

25/85

Solve/Submission

Ranking

# User Language Timing
01 feodorv Cpp 0.02s
02 Robbinb1993 Cpp 0.02s
03 tariqiitju Cpp 0.02s
04 gaexp007895 Cpp14 0.03s
05 prateepm Cpp14 0.15s
06 Morass Cpp14 0.20s
07 twyu0721 Cpp 0.24s
08 abinash Cpp14 0.28s
09 rajdipsaha Cpp14 0.39s
10 Digonta Cpp14 0.40s
11 INUA Cpp14 0.41s
12 fsshakkhor Cpp14 0.41s
13 sahedsohel Cpp14 0.41s
14 Mahmudul_Tushar Cpp14 0.42s
15 adamantium Cpp14 0.42s
16 bhadra Cpp14 0.43s
17 ksohan Cpp14 0.45s
18 froghramar Cpp14 0.49s
19 khatribiru Cpp14 0.50s
20 ahqmrf Cpp14 0.51s
21 swapnil Cpp14 0.54s
Feedback

Your feedback is our precious!



Or call +88 02 9853138 for support