fork download
copy 
  1. /*
  2. プログラミングのお題スレ Part11 
  3. https://m...content-available-to-author-only...h.net/test/read.cgi/tech/1524570314/533
  4.  
  5. 533 名前：デフォルトの名無しさん[sage] 投稿日：2018/06/22(金) 00:11:10.49 ID:3MP35Wby
  6. お題：
  7. ある数値nが与えられた時に、次の条件を満たす２つの数値a,bを求め、表示するプログラムを作成しなさい。
  8. ●aとbの最小公倍数がnとなる
  9. ●a<bかつaとbの差(b-a)が最小となる
  10.  
  11. 例：n= 360→a= 36,b= 40
  12. 　　n=1000→a=125,b=200
  13.  
  14.  
  15. 例が間違ってたらゴメン
  16.  */
  17.  
  18. import java.util.ArrayList;
  19. import java.util.Arrays;
  20. import java.util.List;
  21. import java.util.stream.DoubleStream;
  22.  
  23. public class Main
  24. {
  25.     public static void main(String[] args)
  26.     {
  27.         solve(360);
  28.         solve(1000);
  29.         solve(1049760000);
  30.         solve(1338557220);
  31.     }
  32.  
  33.     public static void solve(int n)
  34.     {
  35.         System.out.printf("n=%d → ",n);
  36.         if (n <= 1)
  37.         {
  38.             System.out.println("no answer");
  39.             return;
  40.         }
  41.  
  42.         ArrayList<int[]> list = new ArrayList<>();
  43.         list.add(new int[] { n });
  44.  
  45.         for (int factor = 2; factor * factor <= n; factor++)
  46.         {
  47.             if (n % factor == 0)
  48.             {
  49.                 DoubleStream.Builder builder = DoubleStream.builder();
  50.                 final double _d = 1D / factor;
  51.                 double d = _d;
  52.                 do
  53.                 {
  54.                     builder.accept(d);
  55.                     d *= _d;
  56.                     n *= _d;
  57.                 } while (n % factor == 0);
  58.                 add(list, builder.build().toArray());
  59.             }
  60.         }
  61.         if (n > 1) add(list, 1D / n);
  62.  
  63.         int min = Integer.MAX_VALUE;
  64.         int answer = -1;
  65.         for (int i = 0; i < list.size(); i++)
  66.         {
  67.             int[] is = list.get(i);
  68.             for (int j = i + 1; j < list.size(); j++)
  69.             {
  70.                 if ((i & j) != 0) continue;
  71.                 int[] js = list.get(j);
  72.                 for (int iv : is)
  73.                 {
  74.                     for (int jv : js)
  75.                     {
  76.                         int diff = Math.abs(iv - jv);
  77.                         if (diff < min)
  78.                         {
  79.                             min = diff;
  80.                             answer = Math.min(iv, jv);
  81.                         }
  82.                     }
  83.                 }
  84.             }
  85.         }
  86.  
  87.         System.out.printf("a=%d, b=%d%n", answer, answer + min);
  88.     }
  89.  
  90.  
  91.     static void add(List<int[]> list, double... mul)
  92.     {
  93.         int limit = list.size();
  94.         for (int i = 0; i < limit; i++)
  95.         {
  96.             int[] src = list.get(i);
  97.             int[] dst = new int[src.length * mul.length];
  98.             int pos = 0;
  99.             for (int j : src)
  100.             {
  101.                 for (double m : mul)
  102.                 {
  103.                     dst[pos++] = (int) Math.round(j * m);
  104.                 }
  105.             }
  106.             Arrays.sort(dst);
  107.             list.add(dst);
  108.         }
  109.     }
  110. }
  111.  
Success #stdin #stdout 0.26s 34252KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
n=360 → a=36, b=40
n=1000 → a=200, b=250
n=1049760000 → a=160000, b=164025
n=1338557220 → a=437437, b=437580
https://ideone.com/TJSzrf
お題スレ11-533 演算誤差によるバグあり
language:
Java (HotSpot 12)
created:
7 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!