网站增加keywords关键词有影响吗,wordpress免费服务器,万维网申请网站域名,丹阳翼网首页文章目录欧拉定理#xff1a;欧拉定理性质#xff1a;扩展欧拉定理#xff1a;费马小定理#xff1a;指数循环节费马大定理逆元#xff1a;例题原根定义#xff1a;原根存在条件例题快速幂代码矩阵快速幂原理#xff1a;代码#xff1a;欧拉定理#xff1a;
aφ(n)≡…
文章目录欧拉定理欧拉定理性质扩展欧拉定理费马小定理指数循环节费马大定理逆元例题原根定义原根存在条件例题快速幂代码矩阵快速幂原理代码欧拉定理
aφ(n)≡1 (mod n) 其中 gcd(a,n)1 欧拉函数是小于x的整数中与x互质的数的个数一般用φ(x)表示。特殊的φ(1)1。 欧拉函数模板
// 直接求
long long Euler( long long n ){long long res n;for( long long i 2 ;i*in;i){if( n %i 0 ){n/i;res res - res/i;}while( n % i0)n/i;}if( n 1 )res res - res/n;return res;
}欧拉定理性质 假设 p, q是两个互质的正整数则 p * q 的欧拉函数为 φ(p * q) φ§ * φ(q) gcd(p, q) 1 。 任意一个整数 n 都可以表示为其素因子的乘积 那么ϕ(n) n( 1−1/p1 )( 1−1/p2 )…( 1−1/pk ) 对于给定的一个素数 p φ( p ) p -1。则对于正整数 n pk φ(n) pk - pk-1
扩展欧拉定理 当(a,m)1时ac≡ac mod φ(m) (mod m) 可以直接指数取模防止指数爆炸 推广到一般情况ab≡ab mod φ(n)φ(n)(mod n)
费马小定理
ap−1≡1 (mod p) 其中 gcd(a,p)1 p为质数 费马小定理是欧拉定理的一种特殊情况。 例题 计算2^100除以13的余数
long long f(long a,long b,long n) //定义函数求a的b次方对n取模
{int t,y;t1;ya;while(b!0){if((b1)1)tt*y%n;yy*y%n;bb1;}return t;
}相关
指数循环节
求证ab (%m)≡ab%φ(m)φ(m)(%m),其中b≥φ(m)
费马大定理
xn yn znn 2时没有正整数解
逆元
对于a和p若 a * inv(a) % p ≡ 1则称inv(a)为a%p的逆元。p为质数
例题
逆元与费马小定理hdu 1576
原根
定义
设m是正整数a是整数若a模m的阶等于φ(m)则称a为模m的一个原根。φ(m)表示m的欧拉函数 如果g是P的原根那么gi mod P的结果两两不同有gp-1 1 (mod P) ,P是素数
原根存在条件
原根存在的条件有以下几个 定理一设p是奇素数则模p的原根存在 [3] 定理二设g是模p的原根则g或者gp是模p2的原根 定理三设p是奇素数则对任意α模pα的原根存在 定理四设α1若g是模pα的一个原根则g与gpα中的奇数是模2pα的一个原根。
例题
Poj 1284 Primitive Roots
快速幂
这个就不介绍了。。。老熟人
代码
ll poww(ll a,ll b)
{int ans1;int basea;while(b){if(b1)ansans*base%mod;basebase*base%mod;b1;}return ans%mod;
}矩阵快速幂
由快速幂延伸而来将数延伸为矩阵原理类似
原理
快速幂矩阵 矩阵乘法左矩阵的第一行乘以右矩阵的第一列分别相乘乘完后相加 单位矩阵 nn的矩阵 mat ( i , i )1; 任何一个矩阵乘以单位矩阵就是它本身 n单位矩阵n 可以把单位矩阵等价为整数1。单位矩阵用在矩阵快速幂中
代码
typedef long long ll;
const int mod 1e9 7;
const int MAXN 10005;//矩阵的大小
struct Mat {ll m[MAXN][MAXN];
}ans, a;//ans为结果矩阵a为输入矩阵
Mat Mul(Mat a, Mat b, int n) {//计算矩阵a乘矩阵bn为矩阵的大小Mat c;//临时矩阵cmemset(c.m, 0, sizeof(c.m));for (int i 1; i n; i)for (int j 1; j n; j)for (int k 1; k n; k)c.m[i][j] (c.m[i][j] (a.m[i][k] * b.m[k][j]) % mod) % mod;return c;
}
Mat _power(Mat a, int b, int n) {//计算a^bn为矩阵的大小for (int i 1; i n; i)//构造单位矩阵ans[i][i] 1;while (b) {if (b 1)ans Mul(ans, a, n);a Mul(a, a, n);b 1;}return ans;
}
