Hard
You are given a 2D integer array, queries
. For each queries[i]
, where queries[i] = [ni, ki]
, find the number of different ways you can place positive integers into an array of size ni
such that the product of the integers is ki
. As the number of ways may be too large, the answer to the ith
query is the number of ways modulo 109 + 7
.
Return an integer array answer
where answer.length == queries.length
, and answer[i]
is the answer to the ith
query.
Example 1:
Input: queries = [[2,6],5,1,73,660]
Output: [4,1,50734910]
Explanation: Each query is independent.
Example 2:
Input: queries = [[1,1],[2,2],[3,3],[4,4],[5,5]]
Output: [1,2,3,10,5]
Constraints:
1 <= queries.length <= 104
1 <= ni, ki <= 104
import java.util.ArrayList;
import java.util.List;
public class Solution {
private static final int MOD = 1_000_000_007;
private long[][] tri;
private List<Integer> primes;
public int[] waysToFillArray(int[][] queries) {
int len = queries.length;
int[] res = new int[len];
primes = getPrimes(100);
tri = getTri(10015, 15);
for (int i = 0; i < len; i++) {
res[i] = calculate(queries[i][0], queries[i][1]);
}
return res;
}
private List<Integer> getPrimes(int limit) {
boolean[] notPrime = new boolean[limit + 1];
List<Integer> res = new ArrayList<>();
for (int i = 2; i <= limit; i++) {
if (!notPrime[i]) {
res.add(i);
for (int j = i * i; j <= limit; j += i) {
notPrime[j] = true;
}
}
}
return res;
}
private long[][] getTri(int m, int n) {
long[][] res = new long[m + 1][n + 1];
for (int i = 0; i <= m; i++) {
res[i][0] = 1;
for (int j = 1; j <= Math.min(n, i); j++) {
res[i][j] = (res[i - 1][j - 1] + res[i - 1][j]) % MOD;
}
}
return res;
}
private int calculate(int n, int target) {
long res = 1;
for (int prime : primes) {
if (prime > target) {
break;
}
int cnt = 0;
while (target % prime == 0) {
cnt++;
target /= prime;
}
res = (res * tri[cnt + n - 1][cnt]) % MOD;
}
return target > 1 ? (int) (res * n % MOD) : (int) res;
}
}