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.     static void solve(int n)
  37.     {
  38.         java.util.BitSet primeSet = new java.util.BitSet();
  39.         java.util.BitSet result = new java.util.BitSet();
  40.         for(int i = 1; i <= n && i > 0; i <<= 1) result.set(i);
  41.  
  42.         int sqrtN = (int) Math.sqrt(n);
  43.         for (int p = 3; p <= sqrtN; p += 2)
  44.         {
  45.             if (primeSet.get(p)) continue;
  46.             for (int i = p + p; i <= sqrtN; i += p)
  47.                 primeSet.set(i);
  48.  
  49.             long pp = p * p;
  50.             for (int i = 1; i > 0; i = result.nextSetBit(i + 1))
  51.             {
  52.                 if (i * pp > n) break;
  53.                 result.set((int) (i * pp));
  54.             }
  55.         }
  56.  
  57.         System.out.printf("%d -> %d%n", n, result.stream().asLongStream().sum());
  58.     }
  59. }
Success #stdin #stdout 0.31s 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/z2q0Sj
プログラミングのお題スレ 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!