Factorial to Square
All submissions for this problem are available.
Read problems statements in Mandarin Chinese and Russian as well.
Given a positive integer n, we want to remove some values between 1 and n such that the product of the remaining ones is a perfect square number (i.e. the product = x * x, for some integer x). Meanwhile, we also want to maximize the product. Therefore, we are interested in the number of ways to remove some values to achieve the maximum perfect square product. The answer may be very large, and therefore, you just need to output its remainder by dividing m.
We define the product of an empty set as 1.
The first line contains an integer T denoting the total number of test cases.
In each test case, there are two positive integers n and m in a line separated by a single space.
For each test case, output the answer per line.
- 1 <= T <= 10
- 1 <= n <= 3,000
- 1 <= m <= 109 + 7
Input: 2 2 10 5 10 Output: 2 2
In the first case, you can either remove 2 or remove both 1 and 2. In the second case, you can either remove 2, 3, 5 or remove 1, 2, 3, 5.
|Tags||cook63, dp+bitmask, medium-hard, shangjingbo|
|Time Limit:||1 sec|
|Source Limit:||50000 Bytes|
|Languages:||ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 6.3, CPP14, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, NODEJS, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYPY, PYTH, PYTH 3.5, RUBY, SCALA, SCM chicken, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC|
Fetching successful submissions
If you are still having problems, see a sample solution here.