Si nous trouvons le plus grand i 2 </ sup> qui peut diviser n, la réponse est i et 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
Considérons f (x) = C 1 </ sub> --C 2 </ sub>. F (x) = 2x 2 </ sup> + (ac) x + (bd) Bien sûr, lorsque x = + ∞ et x = -∞, f (x) = + ∞. Le plus petit est f '(x) = 4x + (ac) = 0 → x = (c --a) Quand f ((c --a) / 4) est positif, il n'y a pas d'intersection, quand il est 0, il y a une intersection et quand il est négatif, il y a deux intersections. Deux intersections sont -∞. Comme il est situé en (c --a) / 4 et (c --a) / 4 .. + ∞, il suffit de rechercher x tel que f (x) = 0 dans la dichotomie, puis on calcule l'équation de la droite passant par les deux points. J'ai écrit 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)
À l'exception du fait que le coût doit être calculé à partir des coordonnées, il ne s'agit que du calcul du chemin le plus court du graphique pondéré, il peut donc être résolu par la recherche de priorité de largeur normalement. Cependant, le code suivant devient TLE sauf s'il s'agit de PyPy (rire).
#AC uniquement avec 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])
J'ai pu écrire que c'était naïf, mais bien sûr TLE. Ou même s'il n'y avait qu'un seul B, je ferais TLE avec N = 6000 et B1 = 3000 (rires).
Addendum: J'ai fait le commentaire DP unidimensionnel, mais c'était toujours TLE en Python.
#AC uniquement avec 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