数论
这篇关于数论的随笔，我将近拖了两个星期（大笑），完全就是因为懒，最近闲的没事，就来重蹈覆辙来将这篇随笔写完。这是我第一篇关于数论的随笔，希望大佬们能够提出宝贵的意见。好了，话不多说，上菜!
同余类（剩余类）
说到同余类这个名词，相信很多的小伙伴都能够很明确的知道这个名词的含义，但是为了更好的回顾这些知识点和掌握知识，所以，我觉得还是有必要解释一下。
同余类，即给定一个正整数n，把所有的整数根据模n的结果属于[0,n-1]划分成n类，并且每类都可以表示为Cr=nx+r的形式，这一类数所构成的一个集合称为模n的剩余类。例如这个
完全剩余系
完全剩余系又简称为完系，即给定一个正整数n，有n个不同的模n的剩余类，然后从这n个不同的剩余类中各自选择一个出来构成的新的集合，我们将这个新的集合称为完全剩余系
例如这个
简化剩余系
给定一个正整数n，有φ(n)个不同的模n的余数r与n互质的剩余类，然后从这个φ(n)个剩余类中各自挑选出一个元素所构成的集合，我们称之为简化剩余系。例如
是不是到这里，看到φ(n)就想起了欧拉函数了呢，是的，到了简化剩余系，我们就要开始复制欧拉定理了。
欧拉定理
欧拉定理相对于费马小定理来讲，其对数的约束降低了，也就是费马小定理中p一定要是质数，且满足gcd(a,p)=1,但是对于欧拉定理来说，p可以是任意数，只需要满足gcd(a,p)=1即可，所以从这里是不是可以看出欧拉定理和费马小定理到达联系了呢，没错，当p为质数的时候，φ(p)=p-1这个就是我们的费马小定理了。所以我们按照证明费马小定理的那样的证明方法来证明欧拉定理，即
扩展欧拉定理
扩展欧拉定理的含金量不用我多说了吧，完全将大幂幂拿捏成小幂幂，然后直接快速幂就好了。
这里给出一道需要扩展欧拉定理的题——洛谷5091
洛谷
下面是AC代码：
点击查看代码
/*
*/
/*
对题目的理解：
扩展欧拉定理
*/
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
char s[20000005];
//求解欧拉函数
int get_phi(int n){
int res=n;
for(int i=2;i*i<=n;i++){
if(n%i==0){
res=res/i*(i-1);
while(n%i==0) n/=i;
}
}
if(n>1) res=res/n*(n-1);
return res;
}
//使用扩展欧拉定理进行降幂
int flag=0;
int depow(int phi){
int b=0;
for(int i=0;s[i];i++){
b=b*10+(s[i]-'0');
if(b>=phi) flag=1,b%=phi;
}
if(flag) b+=phi;
return b;
}
//快速幂
int m;
int quickPow(ll a,int b){
int res=1;
while(b){
if(b&1){
res=res*a%m;
}
a=a*a%m;
b>>=1;
}
return res;
}
int a,b;
int main(){
cin>>a>>m;
scanf("%s",s);
int phi=get_phi(m);
b=depow(phi);
cout<<quickPow(a,b)<<endl;
system("pause");
return 0;
}