fork download 
  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.  
  22. public class Main
  23. {
  24.     static int[] prime = new int[65536];
  25.     static
  26.     {
  27.         boolean[] b = new boolean[65536];
  28.         for (int i = 2; i < 256; i++)
  29.         {
  30.             if (b[i]) continue;
  31.             for (int j = i * 2; j < b.length; j += i)
  32.                 b[j] = true;
  33.         }
  34.  
  35.         int size = 0;
  36.         for (int i = 2; i < 65536; i++)
  37.         {
  38.             if (!b[i]) prime[size++] = i;
  39.         }
  40.         prime = Arrays.copyOf(prime, size);
  41.     }
  42.  
  43.     public static void main(String[] args)
  44.     {
  45.         solve(360);
  46.         solve(1000);
  47.         solve(1088391168);
  48.         solve(1049760000);
  49.         solve(1338557220);
  50.     }
  51.  
  52.     public static void solve(int n)
  53.     {
  54.         System.out.printf("n=%d → ", n);
  55.         if (n <= 1)
  56.         {
  57.             System.out.println("no answer");
  58.             return;
  59.         }
  60.  
  61.         ArrayList<int[]> list = new ArrayList<>();
  62.         list.add(new int[] { n });
  63.  
  64.         for (int factor : prime)
  65.         {
  66.             if (factor * factor > n) break;
  67.             if (n % factor == 0)
  68.             {
  69.                 int size = 0;
  70.                 double[] temp = new double[64];
  71.                 final double _d = Math.nextUp(1D / factor);
  72.                 double d = _d;
  73.                 do
  74.                 {
  75.                     temp[size++] = d;
  76.                     d *= _d;
  77.                     n *= _d;
  78.                 } while (n % factor == 0);
  79.                 add(list, Arrays.copyOf(temp, size));
  80.             }
  81.         }
  82.         if (n > 1) add(list, 1D / n);
  83.  
  84.         int min = Integer.MAX_VALUE;
  85.         int answer = -1;
  86.         for (int i = 0; i < list.size(); i++)
  87.         {
  88.             int[] is = list.get(i);
  89.             for (int j = i + 1; j < list.size(); j++)
  90.             {
  91.                 if ((i & j) != 0) continue;
  92.                 int[] js = list.get(j);
  93.                 for (int iv : is)
  94.                 {
  95.                     for (int jv : js)
  96.                     {
  97.                         int diff = Math.abs(iv - jv);
  98.                         if (diff < min)
  99.                         {
  100.                             min = diff;
  101.                             answer = Math.min(iv, jv);
  102.                         }
  103.                     }
  104.                 }
  105.             }
  106.         }
  107.  
  108.         System.out.printf("a=%d, b=%d%n", answer, answer + min);
  109.     }
  110.  
  111.     static void add(List<int[]> list, double... mul)
  112.     {
  113.         int limit = list.size();
  114.         for (int i = 0; i < limit; i++)
  115.         {
  116.             int[] src = list.get(i);
  117.             int[] dst = new int[src.length * mul.length];
  118.             int pos = 0;
  119.             for (int j : src)
  120.             {
  121.                 for (double m : mul)
  122.                 {
  123.                     dst[pos++] = (int) Math.round(j * m);
  124.                 }
  125.             }
  126.             list.add(dst);
  127.         }
  128.     }
  129. }
  130.  
Success #stdin #stdout 0.08s 29792KB
comments (?)
stdin 
Standard input is empty
stdout 
n=360 → a=36, b=40
n=1000 → a=200, b=250
n=1088391168 → a=497664, b=531441
n=1049760000 → a=160000, b=164025
n=1338557220 → a=437437, b=437580
https://ideone.com/vmgMtp
お題スレ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!