两个数论的算法
$ D' m) I, z% z4 ?' n8 {$ d #include( p* F% c) `1 A+ Z8 \" _7 d
using namespace std; J4 y- H8 L# z' \/ l
struct result6 S; J- [9 s2 C/ l1 k$ l6 O- [! P
{' ^9 ^) Z" ?* ]* w8 Y- L/ U
int d;' }1 ?# r4 P% J# |" W
int x;' a$ n# q% j( g2 V; ~
int y;2 u' r K$ m1 ~
};
2 ?( l; |5 w( p! G //d=gcd(a,b)=ax+by/ p, Z. h9 l9 y5 c
result ExtendeEuclid(int a,int b)
* q. U% A: E b9 F2 C2 V {, Y0 j4 G! z" \; y1 ]2 I9 r5 Z
result res;
1 u. j/ o3 f: [( N9 v if(!b)
+ q0 r) e; p" _6 A. [ {
% u4 ` _6 A5 L res.d=a;
' V Q% S/ r6 L$ v res.x=1;' R ]! ? G: _* j3 k+ L! z
res.y=0;
[! r7 x* o0 A7 M$ ^ return res;0 z0 P* V4 l1 c+ h4 A; P# {; A
}% _. {2 H' c$ w
result temp=ExtendeEuclid(b,a%b);
' f9 n! n* D4 F3 U# N1 O res.d=temp.d;( E, v6 R, [1 X. o8 N
res.x=temp.y;
' y7 a: L$ f! G$ r1 w res.y=temp.x-a/b*temp.y;; ]" k* P# k( y# C. E' J
return res;% T. e! b1 P6 {; P" w; a5 `
}
1 ~' \8 L, S* j' z inline long mod(long a,long b)
! F9 m) u3 m& ?8 N: [ {' J- P; v+ H5 J% E" G! J
return (a%b+b)%b;9 u7 E s3 ]9 g/ Q: Z- K( \* h2 ~% w& I
}
& o( t2 }( c. f) r& Q; G8 `8 O" h& o //计算满足ax和b关于n同余的x
# J. y) t- J/ Z- M8 `2 C6 L7 U void ModularLinearEquationSolver(int a,int b,int n)( j! h3 N8 a: \3 g
{9 }2 \2 p( i5 B) c3 a& y# {+ Q) k
2 d0 J! S# u. F) w* c( @
if(a |
发表于 2012-7-31 21:56:58
