E - MUL 問題概要 整数a1,a2,..,aNが与えられる。 ある自然数kを選び、N以下の全てのkの倍数ik(i>=1)についてa_ik = 0にするという操作が可能な時、 a1,a2,...,aNの総和の最大値を求めよ。 1<=N<=100, |ai| <= 109 解法 MinCutする。 1〜Nの整数をノードとし…

B - GCDロボット 問題概要 N,Z,aiが与えられる。 全てのiについて、gcd(X,a[i])=gcd(Z,a[i])なる最小のXを求めよ。 1<=N<=105,1<=Z,a[i]<=1018 解法 答えから書くと、lcm_(0<=i

問題 問題概要 Kの正の倍数の10進数での各桁の和として最小のものを求めよ。 2<=K<=105 解法 1を以下の2種類の操作でKの倍数にすることを考える。 1. 1増やす 2. 10倍する この2種類の操作で全ての自然数が作れる。 また、1の位の数が9の時には1を使わないと…

問題 問題概要 文字列Sが与えられる。 Sを各々が並び替えれば回文にできるような部分文字列に分割するときその最小数を求めよ。 1 <= |S| <= 2*105 解法 回文条件を言い換えると、「文字列の中に奇数回出てくるようなアルファベットはたかだか1種類である」…