問題文の条件を言い換えると「任意のに対してはで割り切れるか？」です． よってこれを判定すればよいです．
判定方法は愚直に前から見てもいいですし，個すべての最大公約数がで割り切れるかどうかでも判定することができます．
