モジュラ逆 - Javaコーディング

Question

助けてください。私はこのノンストップに取り組んできましたが、それを正しくすることはできません。私が持っている問題は、逆数のために得られる出力が常に1であるということです。

これは私が持っているコードです（GCDを計算して、それも^ -1を計算するように修正しようとしています）。

import java.util.Scanner; 

public class scratchwork 
{ 


    public static void main (String[] args) 
    { 
     Scanner keyboard = new Scanner(System.in); 

     long n, a, on, oa; 
     long gcd = 0; 

     System.out.println("Please enter your dividend:"); 
     n= keyboard.nextLong(); 

     System.out.println("Please enter your divisor:"); 
     a= keyboard.nextLong(); 

     on= n; 
     oa= a; 

     while (a!= 0) 
       {gcd=a; 
        a= n% a; 
        n= gcd; 
     } 

     System.out.println("Results: GCD(" + odd + ", " + odr + ") = " + gcd); 

     long vX; vS; vT; vY; q; vR; vZ; m; b; 

     vX = n; vY=a; 
     vS = 0; vT = 1; m=0; b=0; 
     while (a != 0) 
     { 
      m=vT;; 
       b=vX; 
       q = n/a; 
       vR = vS - q*vT; 
       tZ = n - q*a; 
       vS = vT; n = da; 
       vT = tY; dY = vZ; 

     } 

     if (d>1) System.out.println("Inverse does not exist."); 
     else System.out.println("The inverse of "+oa+" mod "+on+" is "+vT); 
    } 
} 

Answer 1

変数の宣言を確認できますか？整数をdoubleと混合すると、数値は丸められます。

while (a != 0) 
     { 
      m=vT;; 
       b=vX; 
       q = n/a; 
       vR = vS - q*vT; 
       tZ = n - q*a; 
       vS = vT; n = da; 
       vT = tY; dY = vZ; 

     } 

Answer 2

あなたが投稿したコードされていません。あなただけの逆をしたい場合はとにかく、ジュストMath.pow(a, -1);

を使用する。また、第二のループでは、あなたはそれが永遠にループがします「」ように設定はありませんそれが使用する変数の大部分を宣言し、したがって賦課しません。最も重要なのは、変数vが結果を出力するために使用する変数が、投稿コード内のどこにも定義されておらず割り当てられていないことです。

Answer 3

@Justin、 ありがとうございます。私は各ループの変数をどのように表示するかを知ることができました。私は基本的にループをGCDループに入れなければならなかった...それがそれだった。 2週間分の作業と私はループがどこにあったのか分かりました。

申し訳ありませんが、私はここで幸せなダンスをしています。ここで

Answer 4

は、Javaに簡単に翻訳可能である必要があり、Pythonでソリューションです：

def euclid(x, y): 
    """Given x < y, find a and b such that a * x + b * y = g where, g is the 
    gcd of x and y. Returns (a,b,g).""" 
    assert x < y 
    assert x >= 0 
    assert y > 0 

    if x == 0: 
     # gcd(0,y) = y 
     return (0, 1, y) 
    else: 
     # Write y as y = dx + r 
     d = y/x 
     r = y - d*x 

     # Compute for the simpler problem. 
     (a, b, g) = euclid(r, x) 

     # Then ar + bx = g  --> 
     #  a(y-dx) + bx = g --> 
     #  ay - adx + bx = g --> 
     #  (b-ad)x + ay = g 
     return (b-a*d, a, g) 

def modinv(x, n): 
    (a, b, g) = euclid(x%n, n) 
    assert g == 1 

    # a * x + b * n = 1 therefore 
    # a * x = 1 (mod n) 
    return a%n 

それはスタックを使用していますが、ユークリッドのアルゴリズムはOをとる（n個のログを記録）の手順は、スタックオーバーフローを持たないようにしない限り、あなたの数字は天文学的に高いです。また、ある程度の努力を払って非再帰バージョンに変換することもできます。