結果
問題 |
No.321 (P,Q)-サンタと街の子供たち
|
ユーザー |
|
提出日時 | 2015-12-14 04:17:49 |
言語 | Ruby (3.4.1) |
結果 |
AC
|
実行時間 | 271 ms / 2,000 ms |
コード長 | 879 bytes |
コンパイル時間 | 77 ms |
コンパイル使用メモリ | 7,680 KB |
実行使用メモリ | 12,544 KB |
最終ジャッジ日時 | 2024-07-06 21:55:28 |
合計ジャッジ時間 | 7,253 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 41 |
コンパイルメッセージ
Syntax OK
ソースコード
#!/usr/bin/ruby #coding:utf-8 def egcd(x,y) return [x,1,0] if y==0 g,a,b=egcd(y,x%y) [g,b,a-x/y*b] end a,b=gets.split.map(&:to_i).sort if b==0 gets;p $<.count{|e| x,y=e.split.map(&:to_i) x==0&&y==0 } elsif a==0 gets;p $<.count{|e| x,y=e.split.map(&:to_i) x%b==0&&y%b==0 } else g=a.gcd b a/=g b/=g z=egcd(a,b) gets;p $<.count{|e| x,y=e.split.map{|e|e.to_i.abs}.sort next if x%g!=0 || y%g!=0 x/=g y/=g #p z #p z[1]*x*b #((QQ-PP)n+z2XP+z1XQ-Y)%gcd(2P,2Q)==0 g0=(2*a).gcd(2*b) _z=b*b-a*a w=z[2]*x*a+z[1]*x*b-y #zn+w%g0==0 #zn%g0==-w%g0 #p [-w,_z,g0] -w%_z.gcd(g0)==0 =begin α=z[1]*x β=z[2]*x #p α #p β p a*β+b*α-y #(β-2d)A + (α-2b)B == y #2Ad + 2Bb == Aβ+Bα-y w=egcd(2*a,2*b) p w[0] next if p (a*β+b*α-y)%w[0]!=0 true #o=w[1]*(a*β+b*α-y);q=w[2]*(a*β+b*α-y) #β-2*o>=0 && α-2*q =end } end