It was the same even if there was no collision because the speed was taken over, thinking that "the collision time must be calculated and processed in order, it is very difficult!". It was hooked and killed.
The answer is that D is divided by the total speed and rounded up.
N, D = map(int, input().split())
x = list(map(int, input().split()))
v = list(map(int, input().split()))
t = sum(v)
print((D + t - 1) // t)
I couldn't solve it. I was wondering if Fermat's little theorem was involved, but I couldn't think of mathematical conversion.
Addendum: A b c </ sup> </ sup> is A b × c </ sup> is a rudimentary math in the beginning. Here A P ! </ sup> is A P × (P-1) × (P-2)! </ Sup> = A P × (P-2)! × (P-1) </ sup > = A P × (P-2)! P-1 </ sup> </ sup>. From Fermat's theorem, A P × (P-2) If! </ sup> is prime to P, then A P! </ sup> = 1 (mod P). You only have to judge if it is.
As stated in the problem statement, it is TLE in Python, so the following code must be submitted in PyPy.
def make_prime_table(n):
sieve = list(range(n + 1))
sieve[0] = -1
sieve[1] = -1
for i in range(2, int(n ** 0.5) + 1):
if sieve[i] != i:
continue
for j in range(i * i, n + 1, i):
if sieve[j] == j:
sieve[j] = i
return sieve
readline = open(0).readline
prime_table = make_prime_table(5 * 10 ** 6)
T = int(readline())
result = []
for _ in range(T):
A, P = map(int, readline().split())
if prime_table[P] != P:
result.append(-1)
else:
if A % P == 0:
result.append(0)
else:
result.append(1)
print(*result, sep='\n')
Postscript: It was easier to understand if it was rearranged to A P-1 P × (P-2)! </ Su> </ sup>. 1 P × (P-2)! < / sup> or 0 P × (P-2)! </ sup>, so 1 or 0 is a glance.
One after another: I also passed in Python.
def make_prime_table(n):
sieve = [True] * (n + 1)
sieve[0] = False
sieve[1] = False
for i in range(2, int(n ** 0.5) + 1):
if not sieve[i]:
continue
for j in range(i * i, n + 1, i):
sieve[j] = False
return sieve
def main():
readline = open(0).readline
prime_table = make_prime_table(5 * 10 ** 6)
T = int(readline())
result = []
for _ in range(T):
A, P = map(int, readline().split())
if not prime_table[P]:
result.append(-1)
else:
if A % P == 0:
result.append(0)
else:
result.append(1)
print(*result, sep='\n')
main()
After writing that it can be easily solved by the cumulative product, I was addicted to not thinking about what would happen when A i, j </ sub> was 0.
Calculate the cumulative product excluding 0 for all, each row and each column. Fill the r i </ sub> row from the top or the c i </ sub> column from the left. But if there are still 0s left, then the answer to that query is 0.0 If there are no 0s left, then * O * (1) can be used to calculate the answer to the query using the pre-calculated cumulative product.
readline = open(0).readline
H, W = map(int, readline().split())
A = [list(map(int, readline().split())) for _ in range(H)]
Q = int(readline())
m = 1000000007
total = 1
rows = [1] * H
cols = [1] * W
total0 = 0
rows0 = [0] * H
cols0 = [0] * W
for i in range(H):
for j in range(W):
x = A[i][j]
if x == 0:
total0 += 1
rows0[i] += 1
cols0[j] += 1
else:
total *= x
total %= m
rows[i] *= x
rows[i] %= m
cols[j] *= x
cols[j] %= m
result = []
for _ in range(Q):
r, c = map(lambda x: int(x) - 1, readline().split())
x = A[r][c]
t = total0 - rows0[r] - cols0[c]
if x == 0:
t += 1
if t > 0:
result.append(0)
continue
t = total * pow(rows[r], -1, m) % m * pow(cols[c], -1, m) % m
if x != 0:
t *= x
t %= m
result.append(t)
print(*result, sep='\n')
Recommended Posts