ModEquation | Topcoder Archive

Problem Statement

This problem has a non-standard time limit: 3 seconds.

You are given the ints n and K.

Consider the following modular equation with n variables: (x[0] * x[1] * x[2] * ... * x[n-1]) mod K = v. How many solutions does it have for a given value v?

Formally, we want to find the number of sequences (x[0], x[1], ..., x[n-1]) such that each x[i] is an integer between 0 and K-1, inclusive, and the product of all x[i] gives the remainder v when divided by K.

You are also given a int[] query containing q elements. For each i, let answer[i] be the number of solutions the above equation has when v = query[i].

Return a int[] with q elements. For each i, element i of the return value should be the number (answer[i] mod 10^9 + 7).

Definition

Class:: ModEquation
Method:: count
Parameters:: int, int, int[]
Returns:: int[]
Method signature:: int[] count(int n, int K, int[] query)
(be sure your method is public)

Constraints

n will be between 1 and 50, inclusive.
K will be between 2 and 1,000,000,000, inclusive.
query will contain between 1 and 1,000 elements, inclusive.
Each element in query will be between 0 and (K-1), inclusive.

Examples

```
2
```
```
2
```
```
{0,1}
```
```
Returns: {3, 1 }
```
The correct return value should have two elements: Element 0 of the return value should be the number of solutions of the equation (x[0] * x[1]) mod 2 = 0. Element 1 of the return value should be the number of solutions of the equation (x[0] * x[1]) mod 2 = 1. We have: (0 * 0) % 2 = 0 (0 * 1) % 2 = 0 (1 * 0) % 2 = 0 (1 * 1) % 2 = 1 So, the first equation has 3 solutions and the second equation has 1 solution.
```
2
```
```
4
```
```
{0,1,2,3}
```
```
Returns: {8, 2, 4, 2 }
```
```
6
```
```
6
```
```
{4}
```
```
Returns: {2016 }
```

{0,0,0,1,1,1}

Returns: {1, 1, 1, 1, 1, 1 }

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.