Break through in 2 minutes. Just write.
N = int(input())
if str(N).count('7') > 0:
print('Yes')
else:
print('No')
ABC162C - Sum of gcd of Tuples (Easy)
Break through in 4 minutes. For some reason I accidentally did the C problem first. It took a long time because the judge system was clogged and I could not use online execution. Well, I just wrote the problem sentence, but it seems to be TLE Because it was, I modified it by a constant number of times.
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()
Break through in two and a half minutes. Just add except for 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)
It broke through in 24 minutes. TLE1. N ≤ 4000, so I thought it was a double loop. When I did naive, it became triple, but it was not particularly difficult because it can be cumulatively summed.
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)
I couldn't break through. I thought I could solve it. I'm sorry.
Addendum: gcd (f (k, n) with a sequence of length n consisting of integers greater than or equal to 1 and less than or equal to k {A 1 </ sub>, ..., A n </ sub>} If A 1 </ sub>, ..., A n </ sub>) is the number of 1, the answer is ∑ 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)
Explanation This is the assumed solution of 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