fork download
copy 
  1. /*
  2. プログラミングのお題スレ Part12 
  3. //mevius.5ch.net/test/read.cgi/tech/1538096947/17
  4.  
  5. 17 名前：デフォルトの名無しさん[] 投稿日：2018/10/01(月) 20:03:33.29 ID:IziOBEHB
  6. お題：f(n)::={nを連続するいくつかの正整数の和として表す表し方の総数}とおく
  7. 例えば、15=7+8=4+5+6=1+2+3+4+5よりf(15)=4である
  8. 上限Nが与えられたとき、n<=Nでf(n)が奇数となるようなnをすべて足し合わせた値を求めよ
  9.  
  10. 10 -> 24
  11. 100 -> 665
  12. 1000 -> 18006
  13. 10000 -> 571940
  14. 100000 -> 18010994
  15. 1000000 -> 569929080
  16. 10000000 -> 18001029437
  17. 100000000 -> 569128815672
  18. 1000000000 -> 17994029079715
  19. */
  20.  
  21. class Ideone
  22. {
  23.     public static void main(String[] args)
  24.     {
  25.         solve(10);
  26.         solve(100);
  27.         solve(1000);
  28.         solve(10000);
  29.         solve(100000);
  30.         solve(1000000);
  31.         solve(10000000);
  32.         solve(100000000);
  33.         solve(1000000000);
  34.     }
  35.  
  36.  
  37.     static final int MAX = Integer.MAX_VALUE;
  38.     static final int[] factor;
  39.     static
  40.     {
  41.         int[] temp = new int[(int) Math.sqrt(MAX)];
  42.         temp[0] = 2;
  43.         int n = 1;
  44.         loop: for (int i = 3, j = (int) Math.sqrt(MAX); i <= j; i += 2) {
  45.             for (int k = 3, l = (int) Math.sqrt(i); k <= l; k += 2) {
  46.                 if (i % k == 0) continue loop;
  47.             }
  48.             temp[n++] = i * i;
  49.         }
  50.         factor = java.util.Arrays.copyOf(temp, n);
  51.     }
  52.  
  53.     static void solve(int n)
  54.     {
  55.         if (n < 1) throw new IllegalArgumentException();
  56.         System.out.printf("%d -> %d%n", n, r(n, 1, 0));
  57.     }
  58.  
  59.     private static long r(int n, long cur, int f)
  60.     {
  61.         long ret = cur;
  62.         for (int i = f; i < factor.length && cur * factor[i] <= n; i++) {
  63.             ret += r(n, cur * factor[i], i);
  64.         }
  65.         return ret;
  66.     }
  67. }
Success #stdin #stdout 0.05s 2184192KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
10 -> 24
100 -> 665
1000 -> 18006
10000 -> 571940
100000 -> 18010994
1000000 -> 569929080
10000000 -> 18001029437
100000000 -> 569128815672
1000000000 -> 17994029079715
https://ideone.com/m7oieG
プログラミングのお題スレ Part12-17
language:
Java (HotSpot 12)
created:
5 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!