Atcoder ABC215 振り返り

D問題で以前作成した素因数分解関数が役立ってくれました．
hirohirohirohiros.hatenablog.com

A - Your First Judge【AC】

　言われたとおりやります.

print("AC") if input() == "Hello,World!" else print("WA")

B - log2(N)【AC】

　1WAしてしまいました……純粋にmath.log2(N)とやると，誤差が絡み正確に解けないことが多いです．小数が絡むような操作は，なるべく整数として扱えないか考える必要があります．

import math
N = int(input())
k = 1
ans = 0
while k <= N:
    k *= 2
    ans += 1
print(ans-1)

C - One More aab aba baa【AC】

　順列はitertools.permutations()で生成できます．

import itertools
S, K = input().split()
print("".join(sorted(list(set(itertools.permutations(S))))[int(K)-1]))

D - Coprime 2【AC】

　gcd(a, b) = 1というのは，aとbの最大公約数が1ということです．aとbの最大公約数が1というのは，aとbの約数で等しい数字が1しかないということです．つまり，aとbを素因数分解して，得られた基数で一致するものがなければgcd(a, b) = 1となります．素因数分解の計算量はO(√N)なので，全体の計算量はO(√NM)となり十分間に合います．

def prime_fact(x):
        略
    return prime_dict

N, M = map(int, input().split())
A = [int(i) for i in input().split()]

divisor = set()
for a in A:
    prime_dict = prime_fact(a)
    for i in prime_dict.keys():
        divisor.add(i)

ans = [1]
for i in range(2, M+1):
    prime_dict = prime_fact(i)
    div = 0
    for j in prime_dict.keys():
        if j in divisor:
            break
    else:
        ans.append(i)

print(len(ans))
for i in ans:
    print(i)