Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

Re:其实我不确定高代的做法是不是最快的,但貌似没看见有人这么做啊。。。

Posted by 1064232633 at 2015-06-13 23:02:03 on Problem 1006
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator