1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

CodeIQ:「フィズ・バズ・エクストリーム」問題の解答

1
Last updated at Posted at 2026-03-07

Kawazoe(@riverplus)さんのCodeIQの問題です。
問題のページへのリンクが切れていますが、次のような問題です。

問題->n 以下の正の整数のうち、3, 5, 7, 11, 13, 17, 19, 23, 29, 31 の
   少なくともどれか一つの倍数となるものの総和を求めよ。
   Q1(Normal) n=10^5
   Q2(Hard)  n=10^9

こちらにも情報があります
->https://posfie.com/@riverplus/p/28kb2Ab

包除原理を用いて解けます。素数では複数の数の積と最小公倍数が同じです。
答えは、与えられた素数のすべての組み合わせのうち、
奇数個の数の積の倍数の和-偶数個の数の積の倍数の和です。
ある数xの倍数はx,x*2,x*3・・・・x*k (kはnをxで割った商)ですので、
その和は x+2*x+3*x+・・・・k*x = x*k*(k+1)/2 です。

まずJuliaで解きました。
forループでリスト内の素数(nが小さいときはそれ以下の素数)の
すべての組み合わせを求めて、その積の倍数の和をcalcで求め、
奇数個の組み合わせなら足し、偶数個なら引きます。
nが大きくなっても与えられる素数の数が増えなければこの方法で問題ありません。
Juliaではlist内の要素の組み合わせをもとめる関数cmbinationsがありますので、
Combinatricsというパッケージが使えれば簡単に解けます。

#julia ver 1.41,1.12.1

#import Pkg; Pkg.add("Combinatorics")
using Combinatorics

function solve(n,a)
   function calc(re)
       x = reduce(*,re)
       y = div(n,x)
       return x*div((1+y)*y,2) #x+2*x+...y*x
   end
   ar = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31]
   ar = filter(x->(x<=n),ar)
   msum = 0
   for i in 1 : length(ar)
       for x in combinations(ar,i)
          z = calc(x)
          msum = ifelse(isodd(i),msum+z,msum-z)
       end
   end
   s = msum ==  a ? "ok " : "no "
   println(s,msum) 
end

solve(10^5,3469796305)
solve(10^9,347147851533059033)

Combinatoricsが使えない場合自分で関数を作ります。
combcでは最初に使う数を1から一つずつ後ろにずらしながら、
すべてのi個の組み合わせを求めつつ選んだ数を次々に掛けていって、
i個になったらcalcに送って倍数の和を求め、結果を足してゆきます。

#julia ver 1.41,1.53,1.85,1.12.1

function solve(n,a)
   function calc(re)
      y = div(n,re)
      return re*div((1+y)*y,2) #x+2*x+...y*x
   end
   function combc(m,j,i,ml) #すべての組み合わせを作っている
      if i == 0
         return calc(ml)
      end
      sum = 0
      for k in j : m+1-i   #k->最初に選ぶ数字
         sum += combc(m,k+1,i-1,ml*ar[k])
      end
      return sum
   end
   ar = [3, 5, 7, 11, 13, 17, 19, 23, 29, 31]
   ar = filter(x->(x<=n),ar)
   m = length(ar)
   msum = 0
   for i in 1 : m    #i->選ぶ数字の数    
       z = combc(m,1,i,1)
       msum = ifelse(isodd(i),msum+z,msum-z)
   end
   s = msum ==  a ? "ok " : "no "
  println(s,msum) 
end

solve(10^5,3469796305)
solve(10^9,347147851533059033)

Prologでは、comb/3で組み合わせを一つずつ求め、
calc/3でその組み合わせの積の倍数の和を求めますが、
fn/4のfindall/3でI個の数のすべての組み合わせの倍数の和をもとめ、
foldl/4でまとめてたしあわせます。
solve/4ではそれらの数を組み合わせた数の偶奇によって引いたり足したりします。

%SWI-Prolog ver 7.42,7.64,9.29
%:-initialization(start).   %ideone,Online Prolog Compiler
%start.
:-initialization(start).

mul(X,Y,R):-R is X*Y.

comb(_,0,[]):-!.
comb([_|T],I,R):-comb(T,I,R).
comb([H|T],I,[H|L]):-I1 is I-1,comb(T,I1,L).

calc98(N,L,R):-foldl(mul,L,1,X),Y is N div X,R is X*div((1+Y)*Y,2).

fn98(N,I,L,R):-findall(R1,(comb(L,I,L1),calc98(N,L1,R1)),R2),foldl(plus,R2,0,R).

solve(_,0,_,0).
solve(N,I,L,R):-I1 is I-1,solve(N,I1,L,R1),fn98(N,I,L,X),
    (I mod 2 =:= 1->R is R1 + X;R is R1-X).

start:-
   f(N,A),L=[3,5,7,11,13,17,19,23,29,31],include(>(N+1),L,L1),length(L1,N2),
    (solve(N,N2,L1,R)->(R==A->Str=" ok  ";Str=" no  ");write(fail)),
    write(" "),write(Str),writeln(N->R),fail.
start.

f(100000,3469796305).  
f(1000000000,347147851533059033).  




1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?