Blog of Xay

central europe 08 I题的一点经验...
背景：a是b的倍数
1.如果m是质数，很简单，直接用扩展的欧几里德求b关于m的逆元

2.如果m不是质数，把m质数分解成质数p1,p2,……,pk的积
  然后把a分解成a1*a2，其中a1的质因数只能在p[]中，a2与p[]中的所有质数都互质，即a2与m互质
  同理把b分解成b1*b2，其中b1的质因数只能在p[]中，b2与p[]中的所有质数都互质，即b2与m互质

3.现在问题变成了(a1*a2)/(b1*b2)%m，即(a1/b1)%m*(a2/b2)%m。
  问题分解成了两个问题:
   对于a1/b1%m，可以化为(p1^m1*p2^m2*……*pk^mk)/(p1^n1*p2^n2*……*pk^nk)%m，即p1^(m1-n1)*p2^(m2-n2)*……*pk^(mk-nk)%m
   对于a2/b2%m，b2与m互质，则可以直接求出b2关于m的逆元化为a2*b2^(-1)%m.

4.于是，问题解决，时间复杂度约为O(sqrt(m) + log(m))