XGCD（拡張ユークリッド互除法）の計算方法は以下の通りです。 基本的な考え方 XGCDは、2つの整数の最大公約数（GCD）を求めるだけでなく、そのGCDを線形結合として表すための方法です。つまり、整数 a と b に対して、次の形で表現できます： GCD(a, b) = ax + by ここで、x と y は整数です。 計算手順 ユークリッドの互除法を使ってGCDを求める a を b で割り、余り r を求めます。 次に、b を r で割り、余りを求めます。 このプロセスを余りが 0 になるまで繰り返します。最後に非ゼロの余りが GCD です。 拡張ユークリッドのアルゴリズムを適用 ユークリッドの互除法の過程で、各ステップでの商を記録します。 逆算して、GCD を ax + by の形に表現します。 具体例 例えば、a = 30, b = 21 の場合を考えます。 GCDの計算 30 ÷ 21 = 1 余り 9 21 ÷ 9 = 2 余り 3 9 ÷ 3 = 3 余り 0 よって、GCD(30, 21) = 3 逆算してxとyを求める 3 = 21 - 2 × 9 9 = 30 - 1 × 21 これを代入していくつかのステップを経て、最終的に x と y を求めます。 結果 この例では、GCD(30, 21) = 3 で、x と y の具体的な値も求めることができます。 この方法を使えば、任意の整数に対して XGCD を計算することができます。もし具体的な数値での計算が必要であれば、教えてくださいね！