费马小定理、欧拉定理以及扩展欧拉定理(2019南京网络赛 B super_log)
发布时间
阅读量：
阅读量
杂谈
- 数论实在是太菜，以至于碰到数论题基本只有两种选项：跳过or死磕n小时，而数论又是不得不逾越的一道坎，就从几个基本定理开始吧。
费马小定理
- 在p是素数的情况下，对任意整数 x 都有x^p \equiv x \:(mod \:p)
- 若x无法被p整除，则有x^{p-1} \equiv 1\:(mod \: p)
- 利用这个性质，在p是素数的情况下， 很容易求一个数的逆元：将式子变形，得到x \times x^{p-2} \equiv 1\:(mod\:p)
- 因此可以通过快速幂求出逆元。
欧拉定理
- 当 x 和 p 互素，我们有x^{\varphi(m)} \equiv 1 \: (mod \: p)成立
- 不难看出，当p是素数时，有\varphi(p)=p-1，因此欧拉定理可以看作费马小定理的推广。
扩展欧拉定理
- 我们再推广欧拉定理：
- a^c\equiv\begin{cases} a^{c\:mod\:\varphi(m)},\qquad \qquad gcd(a,m)=1 \\ a^c,\qquad \qquad \qquad \quad \:gcd(a,m)\neq1,c
以上第2、3条称作广义欧拉定理 ，适用于指数爆炸 的情况。
就差不多整理到这里，贴道例题吧。2019南京网络赛 super_log
代码
#include <bits/stdc++.h>
using i64 = long long;
i64 mm(i64 x, i64 m) {
return x < m ? x : x % m + m;
}
i64 pow64(i64 a, i64 b, i64 m) {
i64 result = 1;
while(b) {
if(b & 1) result = mm(result * a, m);
a = mm(a * a, m);
b >>= 1;
}
return result;
}
const int N = 1001000;
int phi[N] = {0, 1};
void caleuler()
{
for (int i = 2; i < N; i++)
if (!phi[i])
for (int j = i; j < N; j += i)
{
if (!phi[j]) phi[j] = j;
phi[j] = phi[j] / i * (i - 1);
}
}
int t;
int a, b, m;
int calc(int a, int b, int m) {
if(m == 1) return 1;
if(!b) return 1;
int p = phi[m];
int x = calc(a, b - 1, p);
return pow64(a, x, m);
}
int main() {
caleuler();
std::scanf("%d", &t);
for(int i = 0; i < t; ++i) {
std::scanf("%d%d%d", &a, &b, &m);
std::printf("%d\n", calc(a, b, m) % m);
}
}
AI写代码全部评论 (0)
还没有任何评论哟~