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)\$.
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
Print \$N\$ integers, the elements of array
Aafter performing the program modulo \$(10^9 + 7)\$.
\$1 ≤ N, M ≤ 10^5\$
\$1 ≤ B[i] ≤ N\$
\$1 ≤ A[i], C[i] ≤ 10^5\$
4 3 1 2 3 4 1 2 3 13 29 71
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?