コンテスト中最初に挑んだが解けず、その後も結局解けなかった。gcd convolution を思い出せなかった。 問題へのリンク 問題概要 長さ の正の整数からなる数列 、 が与えられる。これらの数列に対して 個のクエリが与えられる。 【クエリ】 正の整数 が与え…

貴重な区間篩の問題 問題へのリンク editorial 問題概要 2 つの正の整数 が与えられる。以下の条件を満たす整数 の個数を求めよ。 の相異なる素因数の個数が素数個 制約 考えたこと が小さいので、それを活かした解法が考えられそう。具体的には区間篩が使え…