一名提高选手的数论之路（一）

本文主要是介绍一名提高选手的数论之路（一），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

以后要写这个系列，一步步的学习数论^_^
1.首先是数论里用处非常大的快速幂：
（ksm如此基础的算法我就不多说了吧）

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
using namespace std;
int b,p,m;
int ksm(){b%=m;//注意一点，一定要先取模再算，不取模很容易爆。int ans=1;while(p){if(p&1){ans=(ans*b)%m;}b=(b*b)%m;p>>=1;}return ans;
}
int main(){while(scanf("%d %d %d",&b,&p,&m)==3){printf("%d\n",ksm());}return 0;
}

2.然后应该是欧几里得和线性筛素数，我这里没有代码，我也不贴了。。
3.下来是扩展欧几里得算法，可以求二元一次方程最小解，具体自己看。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
using namespace std;
int exgcd(int a,int b,int &x,int &y){if(b==0){x=1;y=0;return a;}int q=exgcd(b,a%b,y,x);y-=a/b*x;return q;
}
int main(){int a,b,x,y;while(scanf("%d %d",&a,&b)==2){int q=exgcd(a,b,x,y);printf("%d %d %d\n",x,y,q);}return 0;
}

一道经典题目：同余方程
4.欧拉函数 $O(\sqrt x)$ 时间内求出：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
using namespace std;
int cnt=0;
int geteuler(int n){int ans=n;for(int i=2;i<=sqrt(n);i++){if(n%i==0){ans=ans/i*(i-1);while(n%i==0){n/=i;}}}if(n>1)ans=ans/n*(n-1);return ans; 
}
int main(){int n;while(scanf("%d",&n)==1){if(n==0)break;printf("%d\n",geteuler(n));}return 0;
}

5.下来是线性筛欧拉函数，自己搜吧：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
using namespace std;
const int maxn=3000010;
int prime[maxn];
bool vis[maxn];
long long phi[maxn];
int cnt;
void getphi(){phi[1]=1;for(int i=2;i<maxn;i++){if(!vis[i]){prime[++cnt]=i;phi[i]=i-1;}for(int j=1;j<=cnt&&i*prime[j]<maxn;j++){int k=i*prime[j];vis[k]=1;if(i%prime[j]==0){phi[k]=phi[i]*prime[j];break;}else phi[k]=phi[i]*(prime[j]-1);}}
}
int main(){int a,b;getphi();for(int i=1;i<=maxn;i++){phi[i]+=phi[i-1];}while(scanf("%d %d",&a,&b)==2){printf("%lld\n",phi[b]-phi[a-1]);}return 0;
}

6.下来是线性筛约数个数：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
using namespace std;
const int maxn=10000000;
int prime[maxn];
int vis[maxn];
int e[maxn];
int num[maxn];
int cnt;
void getnum(){num[1]=1;for(int i=2;i<maxn;i++){if(!vis[i]){prime[++cnt]=i;e[i]=1;num[i]=2;}for(int j=1;j<=cnt&&i*prime[j]<maxn;j++){int k=i*prime[j];vis[k]=1;if(i%prime[j]==0){num[k]=num[i]/(e[i]+1)*(e[i]+2);e[k]=e[i]+1;}else{num[k]=num[i]*num[prime[j]];e[k]=1;}}}
}
int main(){return 0;
}