[PYTHON] Yukicoder-Wettbewerb 249 Teilnehmerrekord

Yukicoder-Wettbewerb 249 Teilnehmerrekord

Ein schöner Tag 1057

Der erste Tag kann kein wunderbarer Tag sein, da es keinen Kuchen gibt, den ich am Tag zuvor gegessen habe. Wenn also die Anzahl der kurzen Kuchen und Schokoladenkuchen unterschiedlich ist, essen Sie den größeren am ersten Tag. Danach können Sie abwechselnd essen.

A, B = map(int, input().split())

if A == B:
    print(2 * A - 1)
else:
    print(min(A, B) * 2)

B 1058 Nette Nummer

Da die zu berechnende Zahl keinen Bruchteil von 2 oder mehr und 10 5 </ sup> oder weniger hat, handelt es sich nicht um eine Primzahl. Kurz gesagt, das Produkt zweier Primzahlen größer als 10 5 </ sup> ist in aufsteigender Reihenfolge. ..

Finden Sie also eine solche Primzahl angemessen,

>>> for i in range(10**5, 10**5+1000):
...   flag = True
...   for j in range(2, int(sqrt(i))+1):
...     if i % j == 0:
...       flag = False
...       break
...   if flag:
...     print(i)
...
100003
100019
100043
100049
100057
100069
100103
100109
100129
100151
...

Finden Sie das Produkt in aufsteigender Reihenfolge

>>> result = []
>>> for i in [100003,100019,100043,100049,100057,100069,100103,100109,100129,100151]:
...   for j in [100003,100019,100043,100049,100057,100069,100103,100109,100129,100151]:
...     result.append(i*j)
...
>>> print(sorted(set(result))[:10])
[10000600009, 10002200057, 10003800361, 10004600129, 10005200147, 10006000171, 10006200817, 10006800931, 10007200207, 10007601083]

Ich habe es in den Quellcode eingebettet.

N = int(input())

print([1, 10000600009, 10002200057, 10003800361, 10004600129, 10005200147, 10006000171, 10006200817, 10006800931, 10007200207][N - 1])

C 1059 Nice set

Ich konnte nicht durchbrechen.

Erstens sind die Kosten 0 oder 1. Weil das Paar von i, i + 1 Kosten 1 ist. Wenn Sie danach denken, dass es vorbei ist, wenn Sie das fallen lassen, das 0 kostet, wie das eratostinische Sieb, ist es nicht. Wenn es beispielsweise 2, 3 und 6 gibt, betragen die Kosten 1 für das Paar 2 und 3, aber die 3 für das Paar 3 und 6 haben die Kosten 0 und die 3 werden gelöscht. Wenn Sie entfernen, können Sie einen schönen Satz zu Nullkosten erzielen. Mit anderen Worten, Sie können Dinge löschen, die ein gemeinsames Vielfaches zu Nullkosten haben. Dann können Sie mit Union Find das Problem lösen, wie viele Gewerkschaften es gibt.

from sys import setrecursionlimit


def find(parent, i):
    t = parent[i]
    if t < 0:
        return i
    t = find(parent, t)
    parent[i] = t
    return t


def unite(parent, i, j):
    i = find(parent, i)
    j = find(parent, j)
    if i == j:
        return
    parent[i] += parent[j]
    parent[j] = i


setrecursionlimit(10 ** 6)

L, R = map(int, input().split())

parent = [-1] * (R + 1)
for i in range(L, R):
    if find(parent, i) != i:
        continue
    for j in range(i * 2, R + 1, i):
        unite(parent, i, j)
print(sum(1 for i in range(L, R + 1) if find(parent, i) == i) - 1)