添字 GCD 畳み込みの練習問題！ 問題へのリンク 問題概要 長さ の正整数列が 個ある。 各数列から高々 1 個ずつ整数を抜き取って得られる数列は 通り考えられる。そのうち抜き取られた数値が 2 個以上あるようなものすべてについての、「それらの数値の最大…

CodeChef Practice(Easy) GCD Sum

添字 GCD convolution が一躍話題になった問題だった気がする 問題へのリンク 問題概要 長さ の整数列 がある。 の値を 998244353 で割ったあまりを求めよ。 制約 考えたこと 個の値のうちのすべてのペアに対するなにかの総和を求める問題では を満たす につ…

AtCoder AGC 038 C - LCMs (黄色, 700 点)

添字 GCD 畳み込みの練習に 問題へのリンク 問題概要 の格子点上の二点対であって、その二点を結ぶ線分上に格子点をもたないものが何個あるかを数え上げよ。(1000000007 で割ったあまりで) 制約 解法 1：添字 GCD 畳み込み この問題は、線分として 軸や 軸に…

yukicoder No.886 Direct

包除原理練習第二弾なん！ という制約の意味に気がつくのにかなり時間がかかったん。これのおかげで「 の中に の倍数が何個あるか」というのが、 ではなく でできるのんな。 Uncommon へのリンク 問題概要 個の相異なる整数 と、整数 が与えられる。各 に対…

みんなのプロコン 2018 決勝 A - Uncommon (包除原理)(600 点)