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種類である」…

問題 問題概要 ビット列Sが与えられる。 "101" -> "010" の変換ができる。最大何回できるか。 解法 dp[i] = (i番目までの文字で最大何回変換できるか) とおく。 変換には二種類あり、もともとある101を変換するか、変換によってできた101を変換するかである…