两个数论的算法 #include' Q/ _# Y+ ?6 }/ x/ L+ O
using namespace std;- W$ H. R5 k0 D( _
struct result9 ]: ?7 ?) \5 }+ T$ [* v. x. s
{" k3 |6 K' n! p7 D( P) W8 }8 @3 r3 F
int d;
2 j* W# _5 Z6 _5 V1 g int x;
8 o' P& @6 E; M( Z0 Y: d" F int y;
% M' _& ]+ `. I, J- I3 W3 q$ t };% e) @ e; ~' |
//d=gcd(a,b)=ax+by
5 k3 b2 Q: b4 Y result ExtendeEuclid(int a,int b)
, b6 e' p6 N/ ~( B {" r6 F% t3 T" L, s1 u% k$ O
result res; w1 g2 C2 y: `% `+ e1 ?
if(!b). d: W1 @6 z% ^) E( [
{
3 ?, Z" ~' P( V2 N" }0 W res.d=a;
1 }8 S* f/ o4 V! K2 e res.x=1;
7 v6 p0 e1 Y. H" n% v" N( b$ O res.y=0;7 `/ M1 J j0 z v
return res;2 f6 R& v8 a5 U+ {+ ^( f
}; ?2 W' C7 M0 F) H; {' W- a
result temp=ExtendeEuclid(b,a%b);
' P% a8 Y# l* W res.d=temp.d;' [6 n; X/ |" M4 ^6 S/ Q
res.x=temp.y; n3 V( i9 ]! o4 X
res.y=temp.x-a/b*temp.y;
+ ]2 M6 Q8 y- O9 d: {, k return res;
% g- k; T+ k+ e# F D9 u' S2 P0 c: L }
: f# n9 B& s& W- A& P* }) ? inline long mod(long a,long b)& V% ?, Q9 D5 @1 ~' ^5 A
{
4 S4 v! R& h% P4 `* a" s1 G& D& d return (a%b+b)%b;, \9 u9 @6 I! y, ~6 i% z
}
- ?8 B1 T5 L4 E. q8 d: s //计算满足ax和b关于n同余的x
5 r+ E- t( D" |, `$ h( P: S3 Y void ModularLinearEquationSolver(int a,int b,int n)
( I' N0 v) M4 ?+ w& Q: ]5 k; z& a {& `) t1 i/ o3 A
8 c/ s. l" d6 t- j/ n if(a |
发表于 2012-7-31 21:56:58
楼主