0
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:「アフター・ドット」問題の解答

0
Last updated at Posted at 2026-11-07

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