-1

x,y,nを正の整数として、1/x + 1/y = 1/nかつx<=yを満たす解の個数が1000を超える最小のnを求めるプログラムを作りたいのですが、以下のプログラムをpaizaで書いてもtime.outと出てしまいます。どうすれば時間がかからずに答えを求めることができますか?

ヒントとして「a,b(a<=b)を正の整数として、x=n+a,y=n+bとおくと,条件式はn²=abとなる。よって、a,bは、n²の約数に限定される。」と書かれています。

public class Main {
    public static void main(String[] args) throws Exception {
        int n=1;    
        while(true){
            int sum = 0;
            for(int x = n + 1; x <= n * 2; x++) {
                int y = x * n / (x - n);
                if(Math.pow(n,2) == x*y && x <= y){
                    if(x * n % (x - n) == 0) { 
                        sum = sum + 1;
                        if(sum > 1000){
                            break; 
                        }
                    }
                }
                n++;
            }
            System.out.println(n);
        }
    }
}
2
  • 1
    この問題は、公開して良い問題でしょうか。もしそうなら、URLを載せてください。
    – actorbug
    1月24日 21:32
  • 紙で出された物なのでURLは載せられないです。
    – 本さん
    1月25日 5:19

1 件の回答 1

1

実行時間の改善以前に、このプログラムは題意を満たしていません。

  1. このプログラムは終了しません。 ※ while(true)から抜け出すコードがありません。
  2. n=1のときx=2、y=2の解が存在しますがsumがカウントされません。
  3. 約数xと約数yのペアをカウントしているようです。xとyが等しいときを考慮すると約数の個数はsum*2-1だと思います。

まずn=1のときの動作を確認した方がよいです。

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。