AtCoder Beginner Contest D - 2017-like Number Difficulty: 981
Ce thème, nombre premier + somme cumulée
En parlant de nombres premiers, *** Ruby *** a une bibliothèque Prime.
Mettez un nombre premier inférieur ou égal à 100000 dans le hachage, vérifiez si (n + 1) / 2 est dans le hachage et obtenez un nombre similaire à 2017.
Ensuite, trouvez l'apparence d'un nombre similaire à 2017 par la somme cumulée.
Ruby
ruby.rb
require 'prime'
g = Prime::EratosthenesGenerator.new
h = Hash.new(0)
a = 2
while a < 100000
h[a] = 1
a = g.next
end
k = Array.new(100001, 0)
h.keys.each do |x|
k[x] = 1 if h[(x + 1) / 2] == 1
end
1.upto(100000) do |i|
k[i] += k[i - 1]
end
gets.to_i.times do
l, r = gets.split.map(&:to_i)
puts k[r] - k[l - 1]
end
prime.rb
g = Prime::EratosthenesGenerator.new
Utilisez un générateur principal.
rui.rb
1.upto(100000) do |i|
k[i] += k[i - 1]
end
Nous obtenons la somme cumulative. Python
python.py
from sys import stdin
def main():
from collections import defaultdict
from math import sqrt
input = stdin.readline
h = defaultdict(int)
h[2] = 1
for i in range(3, 100000, 2):
for j in range(3, int(sqrt(i)) + 1, 2):
while i % j == 0:
h[j] = 1
i //= j
if i > 1:
h[i] = 1
k = [0] * 100001
for key in h.keys():
if (key + 1) / 2 in h and h[(key + 1) / 2] == 1:
k[key] = 1
for i in range(1, 100001):
k[i] += k[i - 1]
q = int(input())
for _ in range(q):
l, r = map(int, input().split())
print(k[r] - k[l - 1])
main()
prime.py
h[2] = 1
for i in range(3, 100000, 2):
for j in range(3, int(sqrt(i)) + 1, 2):
while i % j == 0:
h[j] = 1
i //= j
if i > 1:
h[i] = 1
Je crée mes propres nombres premiers.
hash.py
if (key + 1) / 2 in h and h[(key + 1) / 2] == 1:
k[key] = 1
Il est nécessaire de confirmer l'existence de la clé du dictionnaire.
| Ruby | Python | |
|---|---|---|
| Longueur du code(Byte) | 344 | 697 |
| Temps d'exécution(ms) | 288 | 692 |
| Mémoire(KB) | 4304 | 7896 |
Site référencé
Recommended Posts