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).