# DCP-115: Hasan and Numbers Back to All Problems

Hard Divide and Conquer > Dynamic Programming

Hasan is a very busy young mathematician and unlike other people of his age, he doesn’t want to waste time playing FIFA. Galib considers hasan be his best buddy and always wants to play FIFA with him. Hasan is a kind hearted mathematician and doesn’t want to be too rude to Galib. So Hasan gives Galib a problem if he able to solve it successfully, then Hasan will play FIFA with him. Galib is very weak in counting so he asks for your help. Hasan gives Galib two integer number N and M. How many N digit numbers using digits of N Galib can make which are also divisible by M. One more thing is that it doesn’t have any leading zeros. Input: ------ The first line contains an integer T( 1<= T <= 25 ) which denotes the number of Test cases. T test cases follow . Each test case contains two integers number N and M. Output: ------- For each test case, print a line “Case x: y” where x is replaced by the test case number and y is the how many N digit numbers Galib can make which are divisible by M. Constraints: ------- 1 <= T <= 25 2 <= N <= 10^18 1 <= M <= 100 Sample Input ------------ 2 104 2 223 4 Sample Output ------------- Case 1: 3 Case 2: 1

### 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

# 11/88

Solve/Submission

### Ranking

# User Language Timing
01 feodorv C 0.27s
02 Morass Cpp14 0.96s
03 akazad_cse13_ruet Cpp14 1.31s
04 anowar1112 Cpp14 1.42s
05 sahedsohel Cpp14 1.64s
06 sifat_117 Cpp14 1.68s
07 Mahmudul_Tushar Cpp14 1.73s
08 as_couple Cpp14 1.75s
09 nmunim Cpp14 1.76s
10 Robbinb1993 Cpp 1.95s
11 alhelal_cse Cpp14 2.84s
Feedback