Kawazoe(@riverplus)さんのCodeIQの問題です。
こちらに問題と解答例があります
->https://sw-logic.com/Portfolio/Programing/CodeIQ/2831.php
こちらにも情報があります。テストケースはここからいただいたようです。
->https://posfie.com/@riverplus/p/HiwOi0C
問題の要約
自然数 n に対して 1<=a,b<=n なる自然数(a,b)の組で a÷b が
有限小数になるものの数をもとめよ
既約分数 a/b に対して、以下が成立します。
a/b が有限小数を表す ⇔ 分母 b が 2,5 以外の素因数を持たない
つまり b=2^i*5^j*k (kは因数として2や5を含まない) とすると、
a が k で割り切れます。(a を k で割った商を a // k で表示します)
また 1<=a<=n で k で割り切れる a の数は n // k です。
そこで b<=n となるすべての i,j に対するすべての k について、
n // k を足し合わせます。
Juliaで書きました。
y が 2^i*5^j です。k には2の倍数はありませんので、1 から n // y
の間の奇数を使っています。また5の倍数もありませんので除外しています。
#julia ver 1.0,1.41,1.53,1.85,1.12.5
function solve(n,v)
total = 0
x = 1
while x <= n
y = x
while y <= n
for k in 1 : 2 : div(n,y)
if mod(k,5) != 0
total += div(n,k)
end
end
y *= 2
end
x *= 5
end
s = total == v ? "ok " : "no "
# println(s,n," -> ",sum) #20206.11.7 12:17 sumをtotalに変更
println(s,n," -> ",total)
end
solve(3,7)
solve(5,21)
solve(10,68)
solve(100,2185)
solve(9999,984098)
solve(10000,994145)
solve(100000000,56485671086)
#solve(452048552624980928,2212460374915106900662)
問題では n<=10^4 なのですがテストケースには非常に大きな数があります。
そこで計算量を減らす工夫をしてみました。
nを 1<=k<=n のすべての k で割った商の合計は、前回投稿した中に
ありますように、双曲線 h*k=n の下の格子点の数として求められます。
->https://telvia.jp/mathB/suretsu/suretsu-z05/
->https://en.wikipedia.org/wiki/Dirichlet_hyperbola_method
しかし今回は K=n // y (y=2^i*5^j) としますと、
k<=Kですので少し工夫が必要です。
k<=nとして計算しますと (K+1)<=k<=n の n // k が足し過ぎになります。
これはグラフの対称性を考え和の順序を入れ替えますと、
H=n // (K+1) として、1<=k<=H の (n // k)-K になります。
そこでこの分を後から引きます。
kが偶数の場合と5の倍数の場合が重複していますので、
それぞれ分母と分子を2,5で割ってから同様に求めて引いています。
ただこれでも計算量が多すぎます。
ここからさらに工夫してO(n^(1/3))くらいの計算量にする方法が
あるらしいのですが、私の能力を超えています。
Picatで書きました。
tableは役に立たないようです。
%Picat 3.9#7 ,vscode
%https://ato.pxeger.com
sumdiv(M,K) = Sum =>
M1 = floor(sqrt(M)),
if K <= M1 then
Sum = sum([M // I : I in 1..K])
else
S = sum([M // I : I in 1..M1]),
Sum0 = S * 2 - M1 * M1,
H=M//(K + 1),
S1 = sum([M // I : I in 1..H]),
Sum = Sum0 - S1 + H*K
end.
sumodd(M,K) = R =>
R = sumdiv(M,K) - sumdiv(M // 2,K // 2).
solve(N) = Sum =>
Sum=0,
X=1,
while (X<=N)
Y=X,
while (Y<=N)
Sum := Sum + sumodd(N,N // Y),
Sum := Sum - sumodd(N // 5,N // (Y*5)),
Y := Y*2
end,
X := X*5
end.
main =>
Data = [(3,7),(5,21),(10,68),(100,2185),(9999,984098),
(10000,994145),(100000000,56485671086)],
%(452048552624980928,2212460374915106900662)
foreach((A,N) in Data)
if R = solve(A) then
Str = cond(R == N, " ok ", " no "),
printf(" %s %w -> %w%n", Str, A, R)
else
printf(" fail %w%n", A).