AtCoder ABC177 Ceci est un résumé des problèmes du concours AtCoder Beginner Contest 177, qui s'est déroulé le samedi 29/08/2020, dans l'ordre du problème A, en tenant compte de la considération. La seconde partie traite du problème de l'ED. Cliquez ici pour la première moitié Le problème est cité, mais veuillez consulter la page du concours pour plus de détails. Cliquez ici pour la page du concours Commentaire officiel PDF
Énoncé du problème Il y a des personnes $ N $ de 1 $ à $ N $ personnes. Vous recevrez des informations de $ M $ indiquant que "les personnes $ A_i $ et les personnes $ B_i $ sont des amis". La même information peut être donnée plusieurs fois. Si $ X $ et $ Y $ sont amis et que $ Y $ et $ Z $ sont amis, alors $ X $ et $ Z $ sont aussi amis. De plus, aucune amitié ne peut être dérivée des informations de $ M $. Evil Takahashi essaie de diviser cette personne $ N $ en plusieurs groupes et de créer une situation où tout le monde n'a «pas d'amis dans le même groupe». Combien de groupes dois-je diviser en un minimum?
En retraçant les connexions des amis, nous étudierons le nombre de personnes connectées (= le nombre d'éléments de l'ami défini dans le commentaire officiel) pour chaque groupe. Afin d'empêcher les amis de faire partie du même groupe, nous avons besoin d'au moins un groupe avec le plus grand nombre d'éléments dans l'ensemble d'amis, ce qui est la réponse à afficher. L'implémentation évite la duplication des calculs en créant et en gérant une liste qui vérifie si les personnes $ 1 $ aux personnes $ N $ appartiennent à un groupe.
abc177d.py
n, m = map(int, input().split())
set_dict = {}
chech_list = [0] * (n + 1)
for i in range(m):
a, b = map(int, input().split())
if a in set_dict:
set_dict[a].add(b)
else:
set_dict[a] = {b}
if b in set_dict:
set_dict[b].add(a)
else:
set_dict[b] = {a}
chech_list[a] = 1
chech_list[b] = 1
ans = 1
for i in range(1, n + 1):
if chech_list[i] == 0:
continue
count = 0
temp_set = set_dict[i]
while len(temp_set) > 0:
x = temp_set.pop()
count += 1
chech_list[x] = 0
for y in set_dict[x]:
if chech_list[y] == 1:
temp_set.add(y)
ans = max(count, ans)
print(ans)
Énoncé du problème Il existe des entiers $ N $. Le $ i $ ème nombre est $ A_i
. Quand " GCD (A_i, A_j) = 1 $ pour tout $ 1 \ leq i <j \ leq N" est maintenu, { A_i} est dit coprimaire par paires. Quand { A_i $} n'est pas coprime par paire et $ GCD (A_1,…, A_N) = 1, { A_i} est dit coprimaire setwise. Déterminez si { A_i $} est coprime par paire, coprime setwise, ou aucun des deux. Cependant, $ GCD (…) $ représente l'engagement maximum.
Je ne pouvais pas penser à un moyen d'accélérer la factorisation principale. Convaincu en tamisant Eratostenes dans le commentaire officiel.
abc177e.py
def gcd(a,b):
if b == 0:
return a
else:
return gcd(b,a%b)
n = int(input())
a_list = list(map(int, input().split()))
a_list.sort()
ans2 = a_list[0]
for i in range(1, n):
ans2 = gcd(ans2, a_list[i])
if ans2 == 1:
break
if ans2 != 1:
print("not coprime")
else:
flag = 1
max_a = a_list[n - 1] + 1
num_flag_list = [True] * max_a
d_list = list(range(0, max_a))
d_list[0] = 1
num_flag_list[0] = num_flag_list[1] = False
for i in range(2, int(max_a**0.5) + 1):
if num_flag_list[i]:
for j in range(i**2, max_a, i):
if num_flag_list[j] == True:
num_flag_list[j] = False
d_list[j] = i
p_set = set()
for a in a_list:
if a == 1:
continue
temp_p_set = set()
while True:
p = d_list[a]
if p not in temp_p_set:
if p in p_set:
flag = 0
break
temp_p_set.add(p)
p_set.add(p)
a = a // p
if a == 1:
break
if flag == 0:
break
if flag == 1:
print("pairwise coprime")
else:
print("setwise coprime")
Merci d'avoir lu la seconde moitié jusqu'à la fin.
Recommended Posts