Percer en 2 minutes. Il suffit d'écrire.
N = int(input())
if str(N).count('7') > 0:
print('Yes')
else:
print('No')
ABC162C - Sum of gcd of Tuples (Easy)
Percer en 4 minutes. Pour une raison quelconque, je faisais d'abord le problème C. Cela a pris beaucoup de temps car le système de juge était obstrué et je ne pouvais pas utiliser l'exécution en ligne. Eh bien, je l'ai juste écrit en fonction de l'énoncé du problème, mais il semble que ce soit TLE Parce que c'était le cas, je l'ai modifié un certain nombre de fois.
def main():
from math import gcd
K = int(input())
result = 0
for a in range(1, K + 1):
for b in range(1, K + 1):
t = gcd(a, b)
for c in range(1, K + 1):
result += gcd(t, c)
print(result)
main()
Faites une percée en deux minutes et demie. Additionnez simplement, sauf lorsque Fizz, Buzz, FizzBuzz, etc.
N = int(input())
result = 0
for i in range(1, N + 1):
if i % 3 == 0 or i % 5 == 0:
continue
result += i
print(result)
Il a percé en 24 minutes. TLE1. N ≤ 4000, donc j'ai pensé que c'était une double boucle. Quand j'ai fait Naive, il est devenu triple, mais ce n'était pas particulièrement difficile car il peut être additionné cumulativement.
def main():
N = int(input())
S = input()
rcs = [0] * N
gcs = [0] * N
bcs = [0] * N
for i in range(N):
if S[i] == 'R':
rcs[i] = 1
elif S[i] == 'G':
gcs[i] = 1
elif S[i] == 'B':
bcs[i] = 1
for i in range(1, N):
rcs[i] += rcs[i - 1]
gcs[i] += gcs[i - 1]
bcs[i] += bcs[i - 1]
result = 0
for i in range(N):
if S[i] == 'R':
for j in range(i + 1, N):
if S[j] == 'R':
continue
elif S[j] == 'G':
result += bcs[N - 1] - bcs[j]
t = 2 * j - i
if t < N and S[t] == 'B':
result -= 1
elif S[j] == 'B':
result += gcs[N - 1] - gcs[j]
t = 2 * j - i
if t < N and S[t] == 'G':
result -= 1
elif S[i] == 'G':
for j in range(i + 1, N):
if S[j] == 'G':
continue
elif S[j] == 'R':
result += bcs[N - 1] - bcs[j]
t = 2 * j - i
if t < N and S[t] == 'B':
result -= 1
elif S[j] == 'B':
result += rcs[N - 1] - rcs[j]
t = 2 * j - i
if t < N and S[t] == 'R':
result -= 1
elif S[i] == 'B':
for j in range(i + 1, N):
if S[j] == 'B':
continue
elif S[j] == 'R':
result += gcs[N - 1] - gcs[j]
t = 2 * j - i
if t < N and S[t] == 'G':
result -= 1
elif S[j] == 'G':
result += rcs[N - 1] - rcs[j]
t = 2 * j - i
if t < N and S[t] == 'R':
result -= 1
print(result)
main()
ABC162E - Sum of gcd of Tuples (Hard)
Je n'ai pas pu percer. Je pensais pouvoir le résoudre. Je suis désolé.
Addendum: gcd (f (k, n) avec une suite de n longueurs {A 1 </ sub>, ..., A n </ sub>} constitué d'entiers entre 1 et k Si A 1 </ sub>, ..., A n </ sub>) est le nombre de 1, la réponse est ∑ i = 1..K </ sub> f (floor) (K / i), N) * i.
N, K = map(int, input().split())
MOD = 10 ** 9 + 7
cache = {}
def f(k, n):
if k == 1:
return 1
if k in cache:
return cache[k]
result = pow(k, n, MOD)
for i in range(2, k + 1):
result -= f(k // i, n)
result %= MOD
cache[k] = result
return result
result = 0
for i in range(1, K + 1):
result += f(K // i, N) * i
result %= MOD
print(result)
Explication C'est la solution supposée de PDF.
N, K = map(int, input().split())
MOD = 10 ** 9 + 7
c = [0] * (K + 1)
for i in range(K, 0, -1):
t = pow(K // i, N, MOD)
for j in range(2, K // i + 1):
t -= c[i * j]
t %= MOD
c[i] = t
result = 0
for i in range(1, K + 1):
result += c[K // i] * i
result %= MOD
print(result)
Recommended Posts