J - GCD β 概要 整数のペア(Ai, Bi)がN個ある。各ペアから1つずつ整数を選び、選んだN個の整数の最大公約数を計算することを考える。計算されうる最大公約数の最大値を求めよ。 制約 1 ≦ N ≦ 5 * 10^4 1 ≦ Ai, Bi ≦ 10^9 方針 最初のペア(A1, B1)のうちどち…

D - DivRem Number 概要 整数Nが与えられる。このときN以下の整数mで、Nを割った時の商とあまりが等しいものはいくつあるか。 制約 1 ≦ N ≦ 10^12 方針 N以下のすべての整数を試すことはできない。 Nをxで割った時の商をr、あまりをqとすると、N = rx + qと…

Problem - D - Codeforces 概要 円周上に等間隔でn個の点があり、いくつかの点同士が線で結ばれており、その辺の数はm本である。 この図形が回転対称(rotationally symmetrical)であるかどうかを判定せよ。 制約 2 ≦ n ≦ 100 000 1 ≦ m ≦ 200 000 方針 回転…

C - GCD on Blackboard 概要 N項の数列Aが与えられる。この数列のうち1項を好きな数字に変えて数列全体のGCDを計算する（数字を変えなくてもよい。）。GCDの最大値を求めよ。 制約 1 ≦ N ≦ 2*10^5 1 ≦ A[i] ≦ 10^9 全体の方針 数字を変更する項を固定する。 …