fork download 
  1. # hard coding N,H(87), from STDIN(79)
  2.  g=->r=9,x{r<0?0:g[r-=1,x]-(g[r,x/=p=r==6?3:r*3+r%2+7]-x*(x+1)/2)*p};p g[10**5],g[10**9]
  3. #g=->r=9,x{r<0?0:g[r-=1,x]-(g[r,x/=p=r==6?3:r*3+r%2+7]-x*x-x)*p};p g[eval *$<]/2
  4. #----+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0
  5.  
  6. # for general parameters(131)
  7. #require'prime';f=->m=31,n{q=Prime.each(m).to_a;(g=->r,x{r<2?0:g[r-=1,x]-(g[r,x/=p=q[r]]-x*x-x)*p})[q.size,n]/2};p f[10**5],f[10**9]
  8. #p f[5,20],f[5,1000],f[1000]
  9. #----+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2----+----3----+----4
  10.  
  11. # just one pair of parameters (ex. 31,10**9 etc. ) from STDIN(119)
  12. #require'prime';eval "m,n=#{gets}q=Prime.each(m).to_a;p (g=->r,x{r<2?0:g[r-=1,x]-(g[r,x/=p=q[r]]-x*x-x)*p})[q.size,n]/2"
  13. #----+----1----+----2----+----3----+----4----+----5----+----6----+----7----+----8----+----9----+----0----+----1----+----2----+----3----+----4
  14. __END__
  15. ○以下提出内容
  16. 【解答】
  17. ・第１問：3469796305
  18. ・第２問：347147851533059033
  19. 【方針】
  20. 奇素数列 p[0]=3, p[1]=5, …, p[9]=31, … に対し、g(r,x)=Σ{1≦k≦x| k は p[0],…,p[r]のいずれかで割り切れる} とする。
  21. この時、
  22. 　g(r+1,x)=p[r+1]*n*(n+1)/2 + g(r,x) - p[r+1]*g(r,n)  ( ただし、n=floor(x/p[r+1]) )
  23. という漸化式が成立する。
  24. ※これは、「p[r+1]の倍数」の和、「p[0]～p[r]いずれかで割り切れる数」の和を足し合わせた数値から、重複している
  25.   「p[r+1]の倍数かつp[0]～p[r]のいずれかで割り切れる数」の和を引いたものである
  26.  
  27. ここで、g(0,x)=p[0]*n*(n+1)/2 ( n=floor(x/p[0]) ) としても良いが、r=-1の分を仮想的に g(-1,x)=0 と拡張しても結果は妥当である。
  28. よって、
  29. 　g(-1,x)=0
  30.   g(r+1,x)=p[r+1]*n*(n+1)/2 + g(r,x) - p[r+1]*g(r,n)  ( ただし、r≧-1, n=floor(x/p[r+1]) )
  31. を実装することで答えを求める。
  32.  
  33. 以下の通り、素数列を固定することで105文字のコードとなった。
  34. 他、素数のインデクスの代わりに、素数そのものの上限をパラメータに取る一般化バージョンでは134文字、
  35. 更にstdinからの入力をパラメータとする ( 例えば 31,10**9 ) バージョンでは120文字となり、いずれも1tweetに収めることができる。
  36.  
  37. 【言語】Ruby
  38.  
  39. 【コード】
  40. # ハードコーディング(105)
  41.  g=->r,x{r<0?0:g[r-1,x]-(g[r-1,x/=p=[3,5,7,11,13,17,19,23,29,31][r]]-x*(x+1)/2)*p};p g[9,10**5],g[9,10**9]
  42.  
  43.  
Success #stdin #stdout 0.01s 7452KB
comments (?)
stdin 
10**9
stdout 
3469796305
347147851533059033
https://ideone.com/dIkSzU
CodeIQ q1560 FizzBuzz extreme
https://c...content-available-to-author-only...q.jp/q/1560
language:
Ruby (ruby 2.5.5)
created:
10 years ago
visibility:
public

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!