COLOCON -Colopl programming contest 2018- C すぬけそだて――ごはん――
https://beta.atcoder.jp/contests/colopl2018-qual/tasks/colopl2018_qual_c
問題概要
以上 以下の整数を0個以上選ぶ。
選んだ整数のうちすべての整数が互いに素であるように選ぶとき、何通りの選び方があるか。
制約
解法
より、それぞれの整数が35以下のどの素数を素因数に持つかについて考えればよい。
35以下の素数の数は11個しかないので、bitで情報を持つことができる。
dp[ ][ ] := 番目の整数までみて、選んだ整数の素因数の状態が であるときの場合の数
というDP配列をつくればよい。
計算量は ( は 以下の素数の数) になり十分間に合う。
(解説には全探索って書いてあったけどよくわからなかった)
Submission #2006870 - COLOCON -Colopl programming contest 2018-
Submission #2006886 - COLOCON -Colopl programming contest 2018-
(↑bit演算使ったら簡潔なコードがかけるよって教えてもらった)