Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
Re:其实我不确定高代的做法是不是最快的,但貌似没看见有人这么做啊。。。In Reply To:其实我不确定高代的做法是不是最快的,但貌似没看见有人这么做啊。。。 Posted by:cjjst123 at 2015-06-06 08:26:56 > 根据中国剩余定理,a,b,c两两互质的时候,单独来看如果每一个同余方程存在根,这个方程组总是有解的。记e(x)为x的欧拉函数, > 对于方程 > x三p(mod a),x三i(mod b),x三e(mod c)的通解是 > x=p*pow(b*c,e(a))+i*pow(a*c,e(b))+e*pow(a*b,e(c))+k*a*b*c > 因为对于任意与x互质的数,x的e(x)次方mod x总是1. > 于是只需要写一个求pow的mod的函数就可以了,直接带公式。 > 果然搞计算机的都是暴力算法流啊,我以为这个题会给很变态的数据的。。。。 是不是少了点东西? 还是我记错了额? x=p*pow(b*c,e(a))*(b*c)+i*pow(a*c,e(b))*(a*c) + e*pow(a*b,e(c))*(a*b) Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator