If we find the largest i 2 </ sup> that can divide n, the answer is i and n ÷ i 2 </ sup>.
n = int(input())
for i in range(10 ** 5, 0, -1):
if n % (i * i) == 0:
print(i, n // (i * i))
break
Consider f (x) = C 1 </ sub> --C 2 </ sub>. f (x) = 2x 2 </ sup> + (ac) x + (bd) Of course, when x = + ∞ and x = -∞, f (x) = + ∞. The smallest is f'(x) = 4x + (ac) = 0 → x = (c --a) When f ((c --a) / 4) is positive, there is no intersection, when it is 0, there is one intersection, and when it is negative, there are two intersections. Two intersections are -∞. Since it is located at (c --a) / 4 and (c --a) / 4 .. + ∞, it is sufficient to search for x such that f (x) = 0 by the dichotomy. After that, the equation of the straight line passing through the two points is calculated. I wrote Gugu.
a, b, c, d = map(int, input().split())
def f(x):
return 2 * x * x + (a - c) * x + (b - d)
t = f((c - a) / 4)
if abs(t) < 1e-6:
print('Yes')
exit()
if t > 0:
print('No')
exit()
ok = 1e12
ng = (c - a) / 4
for _ in range(100):
m = (ok + ng) / 2
if f(m) > 0:
ok = m
else:
ng = m
x1 = ok
y1 = x1 * x1 + a * x1 + b
ok = -1e12
ng = (c - a) / 4
for _ in range(100):
m = (ok + ng) / 2
if f(m) > 0:
ok = m
else:
ng = m
x2 = ok
y2 = x2 * x2 + a * x2 + b
p = (y2 - y1) / (x2 - x1)
q = y1 - p * x1
print(p, q)
Except for the fact that the cost must be calculated from the coordinates, it is only the shortest path calculation of the weighted graph, so it can be solved by breadth-first search normally. However, the following code becomes TLE unless it is PyPy (laugh).
#AC only with PyPy
from math import sqrt
from sys import stdin
from collections import deque
readline = stdin.readline
N, M = map(int, readline().split())
X, Y = map(lambda x: int(x) - 1, readline().split())
pq = [list(map(int, readline().split())) for _ in range(N)]
PQ = [list(map(int, readline().split())) for _ in range(M)]
links = [[] for _ in range(N)]
for P, Q in PQ:
links[P - 1].append(Q - 1)
links[Q - 1].append(P - 1)
q = deque([X])
t = [float('inf')] * N
t[X] = 0
while q:
i = q.popleft()
for j in links[i]:
a, b = pq[i]
c, d = pq[j]
k = t[i] + sqrt((a - c) * (a -c) + (b - d) * (b - d))
if k < t[j]:
t[j] = k
q.append(j)
print(t[Y])
Lost. I could write that it was naive, but of course TLE. Or even if there was only one B, I would TLE with N = 6000 and B1 = 3000 (laughs).
Addendum: I made the commentary DP one-dimensional, but it was still TLE in Python.
#AC only with PyPy
N, Q = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
dp = [0] * (N + 1)
dp[1] = 1
dp[0] = A[0] - 1
for i in range(1, N):
for j in range(i, -1, -1):
dp[j + 1] += dp[j]
dp[j + 1] %= 998244353
dp[j] *= A[i] - 1
dp[j] %= 998244353
print('\n'.join(str(dp[b]) for b in B))
Recommended Posts