結果

問題 No.1747 Many Formulae 2
ユーザー tamura2004tamura2004
提出日時 2021-11-20 16:47:40
言語 Crystal
(1.11.2)
結果
AC  
実行時間 13 ms / 2,000 ms
コード長 5,344 bytes
コンパイル時間 27,065 ms
コンパイル使用メモリ 260,720 KB
実行使用メモリ 8,372 KB
最終ジャッジ日時 2023-09-02 12:03:08
合計ジャッジ時間 28,727 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 12 ms
8,280 KB
testcase_01 AC 12 ms
8,324 KB
testcase_02 AC 12 ms
8,316 KB
testcase_03 AC 12 ms
8,156 KB
testcase_04 AC 13 ms
8,196 KB
testcase_05 AC 12 ms
8,368 KB
testcase_06 AC 11 ms
8,324 KB
testcase_07 AC 13 ms
8,268 KB
testcase_08 AC 12 ms
8,148 KB
testcase_09 AC 11 ms
8,148 KB
testcase_10 AC 12 ms
8,240 KB
testcase_11 AC 12 ms
8,216 KB
testcase_12 AC 12 ms
8,372 KB
testcase_13 AC 12 ms
8,160 KB
testcase_14 AC 12 ms
8,272 KB
testcase_15 AC 12 ms
8,216 KB
testcase_16 AC 12 ms
8,156 KB
testcase_17 AC 12 ms
8,196 KB
testcase_18 AC 12 ms
8,324 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

# require "crystal/prime"
# 素数クラス
#
# エラストテレスの篩で、自身を割る最小の素数をクラス変数として持つ
# 素数判定と、高速な素因数分解に利用
class Prime
  MAX = 1_000_000
  extend Enumerable(Int32)
  class_getter div : Array(Int32) = sieve(MAX)
  class_getter each : PrimeIterator = PrimeIterator.new(div)

  # エラストテレスの篩
  #
  # ```
  # seive(5) # => [-1, -1, 2, 3, 2]
  # ```
  def self.sieve(n : Int32) : Array(Int32)
    Array.new(n + 1, &.itself).tap do |dp|
      dp[0] = -1
      dp[1] = -1
      m = Math.sqrt(n).ceil.to_i
      2.upto(m) do |i|
        next if dp[i] != i
        (i*i).step(to: n, by: i) do |j|
          dp[j] = i if dp[j] == j
        end
      end
    end
  end

  # 素数判定
  #
  # ```
  # Prime.is_Prime(7) # => true
  # ```
  def self.is_prime?(n)
    div[n] == n
  end

  # 素数列挙（イテレータ・状態を持つ）
  #
  # ```
  # Prime.first(4).to_a # => [2, 3, 5, 7]
  # Prime.first(4).to_a # => [13,17,19,23]
  # ```
  def self.each(&block : Int32 -> _)
    while true
      value = each.next
      break if value.is_a?(Iterator::Stop::INSTANCE)
      yield value.as(Int32)
    end
  end

  # 素因数分解
  #
  # ```
  # Prime.prime_division(72) # => {2 => 3, 3 => 2}
  # ```
  def self.prime_division(n : T) forall T
    Hash(T, T).new(T.zero).tap do |dp|
      while n > 1
        i = T.new div[n]
        dp[i] += 1
        n //= i
      end
    end
  end

  # 素因数（素数の約数）
  #
  # ```
  # Prime.prime_factor(72) # => [2, 3]
  # ```
  def self.prime_factors(n : T) forall T
    # n.prime_division.keys.to_set # to_setは遅い
    Array(T).new.tap do |dp|
      while n > 1
        i = T.new div[n]
        dp << i if dp.empty? || dp.last != i
        n //= i
      end
    end
  end

  # 約数（1と自身を含む）
  #
  # ```
  # Prime.factors(72) # => [1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72]
  # ```
  def self.factors(n)
    PrimeLarge.factors(n)
  end

  # 素数列挙のイテレータ
  private class PrimeIterator
    include Iterator(Int32)
    getter div : Array(Int32)
    getter i : Int32

    def initialize(@div)
      @i = 2
    end

    def next
      while i <= MAX && div[i] != i
        @i += 1
      end
      if i > MAX
        stop
      else
        begin i ensure @i += 1 end
      end
    end
  end
end

# 大きな数の素数クラス
#
# Prime::MAXを超える数を対象
# 試し割法で愚直に求める
class PrimeLarge
  # 素数判定
  #
  # ```
  # PrimeLarge.is_prime?(72) # => false
  # PrimeLarge.is_prime?(97) # => true
  # ```
  def self.is_prime?(n : T) forall T
    ans = true
    m = T.new Math.sqrt(n)
    ans = T.new(2).upto(m).none? do |i|
      n % i == 0
    end
  end

  # 素因数分解
  #
  # ```
  # PrimeLarge.prime_factors(72) # => { 2 => 3, 3 => 2 }
  # ```
  def self.prime_division(n : T) forall T
    Hash(T, T).new(T.zero).tap do |dp|
      m = T.new Math.sqrt(n)
      T.new(2).upto(m) do |i|
        while n.divisible_by?(i)
          dp[i] += 1
          n //= i
        end
      end
      dp[n] += 1 if n != 1
    end
  end

  # 素因数（素数の約数）
  #
  # ```
  # PrimeLarge.prime_factors # => [2, 3]
  # ```
  def self.prime_factors(n : T) forall T
    Array(T).new.tap do |dp|
      m = T.new Math.sqrt(n)
      T.new(2).upto(m) do |i|
        while n.divisible_by?(i)
          dp << i if dp.empty? || dp.last != i
          n //= i
        end
      end
      dp << n if n != 1
    end
  end

  # 約数（1と自身を含む）
  #
  # ```
  # PrimeLarge.factors(72) # => [1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36, 72]
  # ```
  def self.factors(n : T) forall T
    Array(T).new.tap do |dp|
      m = T.new Math.sqrt(n)
      T.new(1).upto(m) do |i|
        next unless n.divisible_by?(i)
        dp << i
        dp << n // i if i * i != n
      end
    end.sort
  end
end

# 素数関連メソッドの拡張
struct Int
  # 素数判定
  #
  # ```
  # 7.prime? # => true
  # ```
  def is_prime?
    if self > Prime::MAX
      PrimeLarge.is_prime?(self)
    else
      Prime.is_prime?(self)
    end
  end

  # 素因数分解
  #
  # ```
  # 72.prime_division # => {2 => 3, 3 => 2}
  # ```
  def prime_division
    if self > Prime::MAX
      PrimeLarge.prime_division(self)
    else
      Prime.prime_division(self)
    end
  end

  # 素因数
  #
  # ```
  # 72 # => [2, 3]
  # ```
  def prime_factors
    if self > Prime::MAX
      PrimeLarge.prime_factors(self)
    else
      Prime.prime_factors(self)
    end
  end

  # 約数
  #
  # ```
  # 12.factors # => [1, 2, 3, 4, 6, 12]
  # ```
  def factors
    if self > Prime::MAX
      PrimeLarge.factors(self)
    else
      Prime.factors(self)
    end
  end

  # 三角数
  #
  # Ti = 1+2+3+...+i = i(i+1)//2の時
  # 自身以下の最大の三角数のiを求める
  # 三角数は自身を正の整数に分割できる最大数
  def trinum_index
    (Math.sqrt(self * 8 + 1).to_i64 - 1) // 2
  end
end


a = gets.to_s.chars.map(&.to_i64)
n = a.size

ans = 0_i64
(1<<(n-1)).times do |s|
  ans += 1 if calc(a,s).is_prime?
end
pp ans

def calc(a,s)
  n = a.size
  ans = 0_i64
  cnt = a[0]
  (n-1).times do |i|
    if s.bit(i) == 1
      ans += cnt
      cnt = a[i+1]
    else
      cnt *= 10
      cnt += a[i+1]
    end
  end
  ans + cnt
end
0