【今日の精進】ABC195F - Coprime Present

毎日格上の問題を倒すやつの91日目です。

問題リンク

atcoder.jp

問題概要

以上 以下のすべての整数の部分集合であって、どの二つも互いに素であるようなものの個数を求めてね。

解法

幅が狭いのが意味深すぎます。

それぞれの整数について、共通の素数で割れなければよくて、その素数は 以下を考えればよいです。

よって、それらすべてについて、すでに使ったかをもってbitDPすればよいです。

提出コード

A,B=map(int,input().split())
prime=[]
for i in range(2,72):
    if i%2!=0 or i==2:
        if i%3!=0 or i==3:
            if i%5!=0 or i==5:
                if i%7!=0 or i==7:
                    prime.append(i)
n=len(prime)
dp=[0]*(1<<n)
dp[0]=1
for i in range(A,B+1):
    bit=0
    for j,k in enumerate(prime):
        if i%k==0:
            bit+=1<<j
    for j in range(1<<n):
        if j&bit==0:
            dp[j|bit]+=dp[j]
print(sum(dp))

感想

最初包除原理とかで迷走したな…