数论学习之起步篇（三）

2019-04-14 19:57发布

站内文章 / 模拟电子
14849 0 1531
1. 求解模线性方程 费马小定理：设a,p为正整数，且p为素数，(p,a)=1,那么a^(p-1)≡1 (mod p) 剩余类：对于整数a及模m，则集合A={x|x≡a(mod m)}称为模m关于a的一个剩余类 简化剩余系：设m为正整数，在与m互质的所有剩余类中，每一个类中取一个数，构成一个集合X，则X称为模m的一个简化剩余系。 模线性方程ax≡b(mod m)的解： 化为ax+my=b (1) 求d=gcd(a,m) (2) 若d是b的因数，继续(3)。否则无解 (3) 求ax0+my0=d (4) x=x0*b/d; y=y0*a/d; (5) x=(x+k*m/d) (mod m) 所以x一共有d个值，分别为k取0,1,2,3~d-1
2. 求 mod m的逆元 对于整数a,m,如果存在整数b,满足ab≡1(mod m),那么称b是a的模m乘法逆元。 要有解，当且仅当gcd(a,m)=1 例题：输入a,m，求相应的乘法逆元，若不存在，输出0 #include #include #include #include #include #include #include #include #include #include #include #define PI acos(-1.0) using namespace std; long long a,m,d,x,y; long long ex_gcd(long long a, long long b, long long &d, long long &x, long long &y) { if (!b) { x=1; y=0; d=a; } else { ex_gcd(b,a%b,d,y,x); y-=(a/b)*x; } } int main () { while(cin>>a>>m) { if (a==m && a==0) break; ex_gcd(a,m,d,x,y); if (d==1) { x=(x%m+m)%m; cout<

3. 模线性方程组与中国剩余定理 中国剩余定理 有以下一组模线性方程，求x x≡b1(mod m1) x≡b2(mod m2) . . . x≡bn(mod mn) 解为：x0≡(b1*M1*y1+b2*M2*y2+……+bn*Mn*yn) mod m 其中Mi=(m1*m2*m3*……*mn)/mi。而Mi*yi≡1(mod mi) #include #include #include #include #include #include #include #include #include #include #include #define PI acos(-1.0) using namespace std; long long m[100],b[100],n; long long d,x,y; void ex_gcd(long long a, long long b, long long &d, long long &x, long long &y) { if (!b) { d=a; x=1; y=0; } else { ex_gcd(b,a%b,d,y,x); y-=(a/b)*x; } } long long chinaR() { long long mm=1,a=0; int i; for (i=0; i>n) { if (!n) break; for (int i=0; i>m[i]>>b[i]; long long a=chinaR(); cout<

热门文章