[Python] Comment obtenir la fraction d'un nombre naturel à grande vitesse
introduction
Merci d'avoir lu cet article! !! Il s'agit de ** Nakazon **, qui a fait ses débuts en programmation en juin 2020!
C'est ma routine quotidienne pour résoudre au moins 5 problèmes AtCorder A-D.
Dans mon article, du point de vue d'un débutant en programmation, Apprentissage et difficultés découvertes à travers les routines quotidiennes Je voudrais vous dire ce qui m'a fait plaisir.
Je vais essayer de faire un article que les mêmes débutants pourront apprendre! Les personnes avancées regardent avec des yeux chaleureux et Nous attendons avec impatience votre sagesse et vos conseils positifs!
Passons au contenu d'aujourd'hui! !!
problème
Cliquez ici pour les problèmes qui ont conduit à l'apprentissage d'aujourd'hui
C - Walk on Multiplication Table https://atcoder.jp/contests/abc144/tasks/abc144_c
En considérant N = 10 dans l'exemple, il y a deux candidats pour i et j, (1, 10) et (2, 5). Considérons la combinaison de i et j qui satisfait N = i * j avec le plus petit i + j. Puis, quand j'ai pensé: "Prenons le numéro!" Je tombe dans l'état de "Quoi? Que dois-je faire?" .. .. Lol
Voici comment obtenir la fraction du nombre naturel N! !!
Puisque N est un maximum de 10 ** 12, il n'est pas possible de rechercher tout à partir de 1 avec une instruction for Cela prend trop de temps, vous devez donc le concevoir.
qiita.rb
N = int(input())
divisors = []
for i in range(1, int(N**0.5)+1):
if N % i == 0:
divisors.append(i)
if i != N // i:
divisors.append(N//i)
divisors.sort()
Si vous recherchez √N (le point tournant du nombre) comme ceci Le fait est que vous pouvez obtenir toutes les fractions.
finalement
Je veux être une personne qui remarque avec un tel élément d'algorithme. C’est incroyable de le remarquer
Recommended Posts