#!/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,z1,z2=egcd(a,b) a/=g b/=g 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 #((QQ-PP)n+z2XP+z1XQ-Y)%gcd(2P,2Q)==0 g0=(2*a).gcd(2*b) z=b*b-a*a w=z2*x*a+z1*x*b-y #zn+w%g0==0 #zn%g0==-w%g0 p [-w,z,g0] -w%z.gcd(g0)==0 } end