Educational Codeforces Round 81 参加記録 （ C. Obtain The String, D. Same GCDs ）

また、久しぶりにcodeforcesに出てみました。4つ解けたけど自信ないです。 終わってみると簡単だったような気もしてくるから不思議です。Dで結構たくさん迷ったんですが。

C Obtain The String

なんか簡単そうなのに時間がかかりました。 s, tは後ろからみます。 あらかじめsの各文字に対してindexを覚えておきます。 tのそれぞれの文字に対してsのどのindexに対応するか順に計算します。このとき二部探索で一番良いのを探しましょう。

def find(i, l):
    mx,mn=len(l),-1
    if l[-1] <= i:
        return l[0]
    idx = mx//2
    while mx-mn>1:
        if l[idx] > i:
            mx,idx=idx,(idx+mn)//2
            continue
        mn,idx=idx,(idx+mx)//2
    return l[idx+1]

from collections import defaultdict
q = int(input())
for _ in range(q):
    s = input().strip()[::-1]
    t = input().strip()[::-1]
    d = defaultdict(list)
    for i, c in enumerate(s):
        d[c].append(i)
    f = 0
    for c in t:
        if c not in d:
            f = True
            break
    if f:
        print(-1)
        continue
    i = -1
    r = 1
    for c in t:
        j = find(i, d[c])
        if i >= j:
            r += 1
        i = j
    print(r)

D. Same GCDs

条件を式変形して a/gcd(a,m)<= k < (m+a)/gcd(a,m) という式を得ます。 ここでkは「m/gcdの約数であってa/gcdの約数でない数」の倍数でないようにする必要があります。 少し前のABCで包除の実装をしたところだったので計算できました。

def prime_decomposition(n):
    i = 2
    table = dict()
    while i * i <= n:
        c = 0
        while n % i == 0:
            n /= i
            c+=1
        if c!=0:
            table[i] = c
        i += 1
    if n > 1:
        table[int(n)] = 1
    return table

def f(N, mn, ds):
    # N以下mn以上のdsのどれでも割れない数
    M = len(ds)
    r = 0
    for i in range(1, 2**M):
        t=0
        l=1
        for j in range(M):
            if i % 2:
                l*=ds[j]
                t += 1
            i = i>>1
        xx = (1 if t%2 else -1)*(N//l - (mn-1)//l)
        r+=xx
    return r

t = int(input())
for _ in range(t):
    a, m = map(int, input().split())
    aa = prime_decomposition(a)
    mm = prime_decomposition(m)
    ds = list()
    gcd = 1
    for key in mm:
        if key in aa:
            gcd *= key**min(aa[key], mm[key])
            if aa[key] >= mm[key]:
                continue
        ds.append(key)
    mx = -(-(a+m)//gcd)-1
    mn = -(-a//gcd)
    print(mx-mn-f(mx, mn, ds)+1)