足跡-sokuseki-

りかの日進月歩の記録

COLOCON -Colopl programming contest 2018- C すぬけそだて――ごはん――

https://beta.atcoder.jp/contests/colopl2018-qual/tasks/colopl2018_qual_c

問題概要

 A 以上  B 以下の整数を0個以上選ぶ。
選んだ整数のうちすべての整数が互いに素であるように選ぶとき、何通りの選び方があるか。

制約
 1 \le A \le B \le 10^{18}
 B - A \le 35

解法

 B - A \le 35 より、それぞれの整数が35以下のどの素数を素因数に持つかについて考えればよい。
35以下の素数の数は11個しかないので、bitで情報を持つことができる。

dp[  i ][  j ] :=  i 番目の整数までみて、選んだ整数の素因数の状態が  j であるときの場合の数

というDP配列をつくればよい。

計算量は  O( N \times 2^p ) (  p  B - A 以下の素数の数) になり十分間に合う。

(解説には全探索って書いてあったけどよくわからなかった)


Submission #2006870 - COLOCON -Colopl programming contest 2018-

Submission #2006886 - COLOCON -Colopl programming contest 2018-
(↑bit演算使ったら簡潔なコードがかけるよって教えてもらった)