考え方 回答例 考え方入力例1を表でまとめるとわかる．各$p$を横に並べ，$p$の指数を標柱に記入している．丸をつけているのは，各$p$の指数の最大値である． $a_{i}$を1に変えた場合に最小公倍数が変化し得るのは「$a_{i}$の素因数$p$の指数$e$が，その他の$…

考え方 回答例 考え方$N$個の円を$1,...,N$の頂点に対応させ，円周が交わるなら辺を張った無向グラフを考える．こうすれば，$(s_{x}, s_{y})$に対応する頂点の集合から，$(t_{x}, t_{y})$に対応する頂点の集合へ到達できるかを判定する問題に帰着する．「中…