結果
問題 | No.864 四方演算 |
ユーザー |
|
提出日時 | 2021-07-24 17:56:39 |
言語 | Crystal (1.14.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,888 bytes |
コンパイル時間 | 11,250 ms |
コンパイル使用メモリ | 293,632 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-07-20 00:21:14 |
合計ジャッジ時間 | 12,420 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | WA * 3 |
other | WA * 27 |
ソースコード
module Math {% if compare_versions(env("CRYSTAL_VERSION") || "0.0.0", "1.2.0") < 0 %} def isqrt(value : Int::Primitive) raise ArgumentError.new "Input must be non-negative integer" if value < 0 return value if value < 2 res = value.class.zero bit = res.succ << (res.leading_zeros_count - 2) bit >>= value.leading_zeros_count & ~0x3 while (bit != 0) if value >= res + bit value -= res + bit res = (res >> 1) + bit else res >>= 1 end bit >>= 2 end res end {% end %} end class PrimeFactor def initialize(@n : Int32) s = (@n + 1) // 2 sieve = Array.new(s, true) if @n < 2 @primes = [] of Int32 return end m = (Math.isqrt(n) - 1) // 2 (1..m).each do |p| if sieve[p] (p*3+1...s).step(p*2+1) do |q| sieve[q] = false end end end @primes = [2] (1...s).each do |p| @primes << p*2+1 if sieve[p] end end def self.sqrt(n : Int) self.new(Math.isqrt(n).to_i32) end getter primes : Array(Int32) record Factor(T), prime : T, exp : Int32 def div(x : T) forall T factors = [] of Factor(T) t = Math.isqrt(x) @primes.each do |p| break if p > t c = 0 while x%p == 0 c += 1 x //= p end factors << Factor.new(T.new(p), c) if c > 0 break if x == 1 end factors << Factor.new(x, 1) if x > 1 factors end def divisors(x : T) forall T factors = div(x) r = divisors_proc(factors, 0, T.multiplicative_identity) r.sort! end def divisors_proc(factors : Array(Factor(T)), i : Int32, c : T) forall T return [c] if i == factors.size r = [] of T (0..factors[i].exp).each do |j| r.concat(divisors_proc(factors, i+1, c * factors[i].prime**j)) end r end end