I translated the solution by the author to his challenge from C++ to Python. It seems to be correct, but I get timeouts for the test cases 6, 9 and 12.
Here is the full challenge description:
Watson gives to Sherlock an array: \$A_1, A_2, ..., A_N\$. He also gives to Sherlock two other arrays: \$B_1, B_2, ..., B_M\$ and \$C_1, C_2, ..., C_M\$.
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 \$(10^9 + 7)\$.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 arrayB
andC
.Output Format
Print \$N\$ integers, the elements of array
A
after performing the program modulo \$(10^9 + 7)\$.Constraints
\$1 ≤ N, M ≤ 10^5\$
\$1 ≤ B[i] ≤ N\$
\$1 ≤ A[i], C[i] ≤ 10^5\$Sample Input
4 3 1 2 3 4 1 2 3 13 29 71
Sample Output
13 754 2769 1508
And here is my code:
import fileinput
import collections
lines = [[int(x) for x in line.split()] for line in fileinput.input()]
[n, m], a, b, c = lines
def one():
return 1
factors = collections.defaultdict(one)
for i in range(0, m):
factors[b[i]] *= c[i] % 1000000007
for i, factor in factors.iteritems():
for j in range(1, n/i + 1):
idx = j*i-1
a[idx] *= factor
a[idx] %= 1000000007;
print ' '.join(map(str, a))
Any idea on how I could increase the performance of my solution?