ABC114

A – 753

問題

解法

入力Xが7, 5, 3かどうかをチェックするだけです

実装

x=gets.to_i
puts (x==7 || x==5 || x==3)  ? "YES" : "NO"

B – 754

問題

解法

文字列の長さが最大で10なので、前から順番に3文字ずつ選んで整数に変換し、753との差の絶対値をとっていき、その最小値を解とすればよいです。

実装

s=gets.chomp
ans=Float::INFINITY
0.upto(s.length-3) do |i|
    ans = (s[i,3].to_i - 753).abs if ans > (s[i,3].to_i - 753).abs
end

C – 755

問題

解法

300点にしては意外と難しかったです。

Nは最大で999999999なので、全ての整数をチェックしていくのは現実的では無いです。

ここで、Nが999999999の時に各桁が7, 5, 3のみからなる数字がどれくらいあるか考えます。

この場合、39なので19,683個しかありません。(なお、七五三数は 7, 5, 3がそれぞれ1回以上現れる必要があるので、これより少なくなります)

よって、全ての七五三数を探索してN以下のものを数え上げればよいです。

実装

「7, 5, 3がそれぞれ1回以上」というのがちょっと面倒です。

ここでは、とりあえず7, 5, 3からなる整数を作っておき、後で各数字が1回以上あるかどうかを判定しています。

N=gets.to_i

l = N.to_s.length
n = ['3','5','7']
m = ['3','5','7']
2.upto(l) do |i|
    tmp = []
    m.each do |j|
        n.each do |k|
            if k.length == i-1
                tmp << k + j
            end
        end
    end
    n += tmp
end

ans = 0
n.each do |v|
    if v.include?('3') && v.include?('5') && v.include?('7')
        if v.to_i <= N
            ans += 1
        end
    end
end
puts ans

D – 756

問題

解法

七五数の条件である、「約数をちょうど75個持つ正の整数」について最初に考えます。

これは素因数分解すると以下の形で表すことができます。
– p74
– p24q2
– p14q4
– p4q4r2

そこで、N!の素因数分解を行い、N!の約数のうち上記のパターンで表せるものを数えていきます。

なお、N!の素因数分解は、1〜Nをそれぞれ素因数分解し、各指数部分を加算していけば求めることが出来ます。

実装

Rubyのpermutationメソッドを使って組み合わせを列挙し、計算結果がN!の約数かどうかをチェックして数え上げていきます。

require 'prime'
N=gets.to_i
h = Hash.new(0)
1.upto(N) do |i|
    i.prime_division.each do |a,b|
        h[a] += b
    end
end

nn = 1
1.upto(N) do |i|
    nn *= i
end
ans = []
h.keys.permutation(3) do |a,b,c|
    tmp = a**4 * b**4 * c**2
    if nn % tmp == 0
        ans << tmp
    end
end
h.keys.permutation(2) do |a,b|
    tmp = a**24 * b**2
    if nn % tmp == 0
        ans << tmp
    end
    tmp = a**14 * b**4
    if nn % tmp == 0
        ans << tmp
    end
end


h.each do |k,v|
    ans << k ** 74 if v >= 74
end

p ans.uniq.size

コメント

タイトルとURLをコピーしました