問題（外部リンク） 1995 -- Raising Modulo Numbers 実装の概要 問題文ではやや難しい表現を使っていますが、出力の仕様に書いてある計算式の通り累乗したものを加算してmodを求めることで解くことができます。 その際、指数部が大きく普通にループを回すと…

問題（外部リンク） 3641 -- Pseudoprime numbers 実装の概要 となっているかを判断する問題ですが、注意点がいくつかあります。 まず、pの値が大きいので乗算を普通のループで計算すると間に合いません。そのためここでは繰り返し二乗法を使います。 また、…

問題（外部リンク） 3292 -- Semi-prime H-numbers 実装の概要 この問題では数字はの形で表されるH-numberしか現れません。 H-primeかどうかの判定は通常の整数に対するエラトステネスの篩を改修することで実現できますが、H-semi-primeかどうかの判定は困難…

問題（外部リンク） 3421 -- X-factor Chains 実装の概要 例えばX=100であれば条件を満たす数列は 1,2,4,20,100 1,5,25,50,100 など計6パターンが有りえますが、ポイントとなるのはXを素因数分解した結果です。であることを考えると2つの2と2つの5をどの順番…

問題（外部リンク） 3126 -- Prime Path 実装の概要 それぞれの素数をグラフの頂点と考え、ある特定の桁だけ数字を変えれば良い場合は距離を1として初期化します。 その後はある頂点から別の頂点までの最短距離を求める問題と考えることができます。ワーシャ…

問題（外部リンク） 2429 -- GCD & LCM Inverse 実装の概要 与えられた最大公約数（GCD）と最小公倍数（LCM）からもともとの2つの整数を逆算する問題。 入力値がlong型なので全パターン試そうとすると間に合いません。また、a+bが最小になるようにという条件…

問題（外部リンク） Prime Number | Aizu Online Judge 実装の概要 あるnが素数かどうかだけでなく、nまでの素数の個数を求める問題なので2,3,...nのように1つ1つ素数かどうかをチェックしていると間に合いません。 そのため、事前に「その数が素数かどうか…

問題（外部リンク） GCD and LCM | Aizu Online Judge 実装の概要 GCD（最大公約数）とLCM（最小公倍数）の求め方については高校の教科書の通りなので特に説明は不要かと思いますが、手計算とは異なり剰余だけ求めれば計算可能です。 GCDとLCMは他の問題で使…