【AtCoder】ABC162-E Sum of gcd of Tuples (Hard)がわからない
スポンサードリンク
配点 : 500 点
問題文
1 以上 K 以下の整数からなる長さ N の数列 {A_1,…,A_N} を考えます。
そのようなものは K^N 個ありますが、その全てについての gcd(A_1,…,A_N) の和を求めてください。
ただし、答えは非常に大きくなる可能性があるため、和を (10^9+7) で割ったあまりを出力してください。
なお、gcd(A_1,…,A_N) は A_1,…,A_N の最大公約数を表します。
制約
- 2 ≦ N ≦10^5
- 1 ≦ K ≦ 10^5
- 入力は全て整数
考えたこと
あ、DP!
DP[a,b]= a番目の数まで考慮したときに、b…B!?何に使うんだ！？
…gcd(2,3,,,,,,…,a,k)は、gcd(gcd(2,3,,,,,,,…,a),k)なので、
kの数だけforループを回せば解ける！！(k≦10^5)
でも、10^9+7で割ったあまりを求める問題だから、DP[N]とかDP[K]でどうにかなるはず…？
DP(K)で考えたとき、DP[2] = 2^N+1であることはわかったけど、3以上のときの構築がわからない。
実験的に、N=3,4のときのK=2,3,4,5ぐらいを出してみたけど、法則性がつかめない。
[2,4,2]は[2,2,4]と昇順に並び替えることができるし、変化量的な考え方すると、[2,0,2]と表記できて、和がNまでになる。0を無視すればGCD的には値は変わらないはず。(ユークリッドの互除法)
（考察70分）無理じゃぁ！
解説PDF
「gcd(A1, …, AN ) = X となる数列 {Ai} がいくつあるか？」という問題を考えます。
最大公約数が X の倍数であるための必要十分条件は、A1, …, AN が全て X の倍数であることで
す。
…天才か？
…競プロやっていったら、思いつくようになるのか？
スポンサードリンク