結果
問題 | No.377 背景パターン |
ユーザー | ciel |
提出日時 | 2017-12-31 22:42:23 |
言語 | Crystal (1.11.2) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 901 bytes |
コンパイル時間 | 2,350 ms |
コンパイル使用メモリ | 217,944 KB |
最終ジャッジ日時 | 2024-11-14 20:18:22 |
合計ジャッジ時間 | 2,754 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
[2mShowing last frame. Use --error-trace for full trace.[0m In [4mMain.cr:39:20[0m [2m 39 | [0m[1mcache[key]=pow(k,key,M) if !cache.has_key?(key)[0m [32;1m^--[0m [33;1mError: expected argument #2 to 'pow' to be Int64, not Float64[0m Overloads are: - pow(x : Int64, y : Int64, m : Int64)
ソースコード
M=1000000007_i64 def pow(x : Int64,y : Int64,m : Int64) z=1_i64 while y>0 z=z*x%m if y%2>0 x=x*x%m y/=2 end z end def prime_division(n) Process.run("factor",["factor",n.to_s]){|io| h=Hash(Int64,Int64).new(0_i64) io.output.gets.not_nil!.split()[1..-1].each{|e|h[e.to_i64]+=1} h.map{|k,v|[k,v]} } end def divisor_totient(a,d,n,t,&blk : (Int64,Int64)->_) if d==a.size blk.call(n,t) else (0..a[d][1]).each{|i| divisor_totient( a,d+1, n*pow(a[d][0],i.to_i64,M), i==0 ? t : t*(a[d][0]-1)*pow(a[d][0],(i-1).to_i64,M),&blk) } end end cache=Hash(Int64,Int64).new h,w,k=ARGF.gets_to_end.split.map(&.to_i64) a=prime_division(h) b=prime_division(w) r=0_i64 divisor_totient(a,0,1_i64,1_i64){|ad,at| divisor_totient(b,0,1_i64,1_i64){|bd,bt| key=w*h/ad.lcm(bd) cache[key]=pow(k,key,M) if !cache.has_key?(key) r=(r+at*bt%M*cache[key])%M } } puts r*pow(w*h%M,M-2,M)%M