개인 노트

감상

abc3 완료
업데이트 로그

A - A*B*C

변수는 A, B, C 세 개가 있다
변수를 두 개로 만들고 싶으므로 ABC\leqk를 AB\leq\lflowor K/C\rflowor(\leqK/C)로 변경합니다.
이렇게 하면 C에 대한 전체 탐색을 하는 동시에 O(1)로 각 C의 값인 AB를 구하면 전체적인 계산량은 O(K) 인접 지역이 양호하다.
\lflowor K/C\rflowor를 질적 인수 분해하는 경우 A, B의 조합이 필요합니다.
만약 사전에 각 값에 따라 계산한다면 A, B의 조합은 O(1)가 필요하다
\lflor K/C\rflor\leqK, 범위 내에서 사전 계산

from collections import Counter
from itertools import accumulate


def integer_factorization_list(n: int):
    """
    入力された整数nを素因数分解し，素因数が列挙されたリストで返却
    Parameters
    ----------
    n : int
        素因数分解したい整数
    Returns
    -------
    integer_factorization_list : lst
        [素因数]の形で素因数が列挙された素因数分解結果
    """
    res = []
    for candidate_of_prime in range(2, int(n ** 0.5) + 1):
        while n % candidate_of_prime == 0:
            n //= candidate_of_prime
            res.append(candidate_of_prime)
    if n > 1:
        res.append(n)
    return res


K = int(input())
# K = 2 * 10 ** 5

cumsum = [0]
for a in range(1, K + 1):
    primes = Counter(integer_factorization_list(a))
    res = 1
    for i in primes.values():
        res *= i + 1
    cumsum.append(res)
    # print(a, primes.values())

cumsum = list(accumulate(cumsum))
# print(cumsum)

ans = 0
for c in range(1, K + 1):
    ans += cumsum[K // c]

print(ans)

B - A^B^C

자연수의 곱셈을 보면 첫 번째가 순환하는 것을 알 수 있다
이 성질을 사용하려면 A ^D (D = B^C) 의 1위가 필요하다
그러면 D를 요구하고 싶지만 A의 곱셈은 일정한 주기로 순환하기 때문에 그 주기로 D의 잉여치를 얻으면 k가 된다.

A, B, C = map(int, input().split())

a_loop = []
res = A
while str(res)[-1] not in a_loop:
    a_loop.append(str(res)[-1])
    res *= A

D = pow(B, C, len(a_loop))

# Dを-1しているのはD mod len(a_loop)とa_loopのインデックスが対応してないから  
ans = a_loop[(D - 1) % len(a_loop)]

print(ans)

C - String Invasion

오른쪽부터 천천히 하는 게 좋을 것 같아요.
설치 시 abab,aba 등 주의하십시오
자세한 설명은 내일 쓰실 것 같아요.

from collections import Counter
S = input()

ans = 0
between_cnt = Counter(S[-2:])
last = ("", -1)
for i in range(len(S) - 3, -1, -1):
    if S[i] == S[i + 1] and S[i] != S[i + 2]:
        ans += len(S) - (i + 2) - (between_cnt[S[i]] - 1)
        last = S[i]
        # print(ans, between_cnt)
        between_cnt = Counter()
        between_cnt[S[i]] += len(S) - i

    else:
        between_cnt[S[i]] += 1

print(ans)