Watson gives to Sherlock an array:
A1, A2, ⋯, AN
. He also gives to Sherlock two other arrays:B1, B2, ⋯, BM
andC1, C2, ⋯, CM
. Then Watson asks Sherlock to perform the following program:for i = 1 to M do for j = 1 to N do if j % B[i] == 0 then A[j] = A[j] * C[i] endif end do end do
Can you help Sherlock and tell him the resulting array A? You should print all the array elements modulo (1000000007).
Input Format
The first line contains two integer numbers N and M. The next line contains N integers, the elements of array A. The next two lines contains M integers each, the elements of array B and C.
Output Format
Print N integers, the elements of array A after performing the program modulo (1000000007).
Sample Input
4 3 1 2 3 4 1 2 3 13 29 71
Sample Output
13 754 2769 1508
If we brute force, it will time out. Please suggest ways on making this efficient.
import java.math.BigInteger;
import java.util.Scanner;
import java.util.StringTokenizer;
public class SherlockArray {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
String line1 = in.nextLine();
StringTokenizer st = new StringTokenizer(line1, " ");
int n = Integer.parseInt(st.nextToken());
int m = Integer.parseInt(st.nextToken());
Long[] b = new Long[m];
String strA = in.nextLine();
String[] stA = strA.split(" ");
BigInteger aBI[] = new BigInteger[n];
for (int ia = 0; ia < stA.length; ia++) {
aBI[ia] = new BigInteger(stA[ia]);
}
String strB = in.nextLine();
String[] stB = strB.split(" ");
for (int ib = 0; ib < stB.length; ib++) {
b[ib] = Long.parseLong(stB[ib]);
}
String strC = in.nextLine();
String[] st3 = strC.split(" ");
for (int ic = 0; ic < m; ic++) {
for (int index = b[ic].intValue(); index <= n; index += b[ic]
.intValue()) {
aBI[index - 1] = aBI[index - 1].multiply(new BigInteger(st3[ic]));
}
}
for (int ia = 0; ia < n; ia++) {
aBI[ia] = aBI[ia].mod(new BigInteger("1000000007"));
System.out.print(aBI[ia] + " ");
}
}
}