第一彈數論的主要内容有以下幾部分：歐拉函數、埃式篩法、分解質因數、歐幾裡得算法、擴充歐幾裡得算法和模線性方程。
1、歐拉函數（連續求n個數的歐拉函數）
#include<iostream>
using namespace std;
int main()
{
int phi[100];// 用于篩法開素數表
int dive[100];//用于儲存1~n的每個數的歐拉函數
int n;
cin>>n;
for(int i=1;i<=n;i++)
{
phi[i]=i;
}
for(int i=2;i*i<=n;++i)
{
if(phi[i]==i)
{
for(int j=i*i;j<=n;j+=i)
{
phi[j]=i;
}
}
}
dive[1]=1;
for(int i=2;i<=n;++i)
{
dive[i]=dive[i/phi[i]];
if((i/phi[i])%phi[i]==0)
{
dive[i]*=phi[i];
}
else
{
dive[i]*=phi[i]-1;
}
}
for(int i=2;i<=n;i++)
cout<<dive[i]<<" ";
}
求單個數的歐拉函數：
int n,i,temp;
while(scanf("%d",&n)!=EOF)
{
temp=n;
for(i=2;i*i<=n;i++)
{
if(n%i==0)
{
while(n%i==0) n=n/i;
temp=temp/i*(i-1);
}
if(n<i+1)
break;
}
if(n>1)
temp=temp/n*(n-1);
printf("%d\n",temp);
}
2、埃式篩法（用于列印素數表）
給出要篩數值的範圍n，找出以内的素數。先用2去篩，即把2留下，把2的倍數剔除掉；再用下一個質數，也就是3篩，把3留下，把3的倍數剔除掉；接下去用下一個質數5篩，把5留下，把5的倍數剔除掉；不斷重複下去.....
#include<iostream>
#include<cmath>
#include<cstring>
using namespace std;
int vis[10000];
int main()
{
int n;
cin>>n;
int m=sqrt(n+0.5);
memset(vis,0,sizeof(vis));
for(int i=2;i<=m;i++)
{
if(!vis[i])
{
for(int j=i*i;j<=n;j+=i)
{
vis[j]=1;
}
}
}
for(int i=2;i<=n;i++)
{
if(vis[i]==0)//最後剩下的vis[i]=0的都是質數
cout<<i<<" ";
}
}
下面貼一個埃式篩法的形象的展示：
3、分解質因數（模闆）
#include<iostream>
#include<cmath>
using namespace std;
int a[10000];//用于儲存第i個質因數的值
int b[10000];//用于儲存第i個質因數的指數
int main()
{
int n;
cin>>n;
int tot;//不同質因數的個數
int temp, i,now;
temp=(int)((double)sqrt(n)+1);
tot=0;
now=n;
for(i=2;i<=temp;++i)
{
if(now%i==0)
{
a[++tot]=i;
b[tot]=0;
while(now%i==0)
{
++b[tot];
now/=i;
}
}
}
if(now!=1)
{
a[++tot]=now;
b[tot]=1;
}
//得到a[i]^b[i]就是n的質因數分解
}
4、歐幾裡得算法 //輾轉相除法
歐幾裡德算法又稱輾轉相除法，用于計算兩個整數a,b的最大公約數。
基本算法：設a=qb+r，其中a，b，q，r都是整數，則gcd(a,b)=gcd(b,r)，即gcd(a,b)=gcd(b,a%b)。
證明：
a可以表示成a = kb + r，則r = a mod b
假設d是a,b的一個公約數，則有 d|a, d|b，而r = a - kb，是以d|r 是以d是(b,a mod b)的公約數
假設d 是(b,a mod b)的公約數，則 d | b , d |r ，但是a = kb +r 是以d也是(a,b)的公約數
是以(a,b)和(b,a mod b)的公約數是一樣的，其最大公約數也必然相等，得證
求最大公約數：
int gcd(int a,int b)
{
return b ? gcd(b,a%b) : a;
}
求最小公倍數：
- int lcm(int a,int b) {
- return a/gcd(a,b)*b;
- }
5、擴充歐幾裡得算法
對于一個等式，a*x+b*y=gcd(a,b)，求一對x,y的算法。
證明：設 a>b。
1，顯然當 b=0，gcd（a，b）=a。此時 x=1，y=0；
2，ab!=0 時 設 ax1+by1=gcd(a,b); bx2+(a mod b)y2=gcd(b,a mod b);
根據樸素的歐幾裡德原理有 gcd(a,b)=gcd(b,a mod b);
則:ax1+by1=bx2+(a mod b)y2; 即:ax1+by1=bx2+(a-(a/b)*b)y2=ay2+bx2-(a/b)*by2;
根據恒等定理得：x1=y2; y1=x2-(a/b)*y2;
這樣我們就得到了求解 x1,y1 的方法：x1，y1 的值基于 x2，y2.
上面的思想是以遞歸定義的，因為 gcd 不斷的遞歸求解一定會有個時候 b=0，是以遞歸可以結束。
int ex_gcd(int a,int b,int &x,int &y)//x、y傳位址的意思是，函數内對x、y的改變也能改變函數外x、y的值，類似于全局變量
{
if(b==0)
{
x=1;
y=0;
return a;
}
int r=ex_gcd(b,a%b,x,y);
int t=x;
x=y;
y=t-a/b*y;
return r;
}
6、模線性方程
ax ≡ b(mod n)，表示ax和b對n取模相等。
1）求解線性不定方程
ax + by = c
先求出一組解，然後考慮如何表示通解，設d = gcd(a, b), 假設c不是d的倍數，則左邊是d的倍數而右邊不是，則方程無解，是以方程有解當且僅當d | c.設c = c' * d。
我們先考慮方程 ax + by = d，這樣由擴充gcd便可求出一組解 （x', y')，則（c'x', c'y')就是原方程的一組解，然後考慮通解：假設有兩組解(x1, y2) ， (x2, y2)，有 ax1 + by1 == ax2 + by2 = c， 移項得： a(x1 - x2) == b(y2 - y1)，消去d後有 a'(x1 - x2) == b'(y2 - y1)。此時a' 和 b' 互素，是以（x1 - x2)一定是b'的倍數，而(y2 - y1)一定是a'的倍數，由此可得到通解：給一組特解(x, y), 通解為(x - kb', y + ka')。
2）求解模線性方程
ax = b(mod n)
其實方程等價于 ax - ny = b, 标準模線性方程，但是得考慮剩餘系。
算法導論上有兩個定理：
定理一：設d = gcd(a, n), 假定對整數x', y', 有d = ax' + ny'， 如果d | b, 則方程ax = b(mod)有一個解的值為x0, 滿足：、
x0 = x'(b / d)(mod n）
定理二：假設方程ax = b(mod n)有解， x0是方程的任意一個解， 則方程對模n恰有d個不同的解， 分别為： xi = x0 + i * (n / d), 其中 i = 1,2,3......d - 1
有了這兩個定理， 解方程就不難了。
void linear_mod_equation (int a, int b, int n, int *sol)
{
int d, x, y;
gcd (a, n, d, x, y );
if (b % d) d = 0;
else
{
sol [0] = x * ( b / d ) % n ;
for (int i = 1; i < d; ++i)
sol[i] = (sol[i - 1] + n / d) % n;
}
}
如果gcd(a, n) == 1, 則方程有唯一解， 即解為a的逆。
long long inv(ll a, ll n)
{
long long d, x, y;
gcd(a, n, d, x, y);
return d == 1 ? (x % n + n) % n : -1;
}
首先看一個簡單的例子：
5x=4(mod3) 解得x = 2,5,8,11,14.......
由此可以發現一個規律，就是解的間隔是3.那麼這個解的間隔是怎麼決定的呢？
如果可以設法找到第一個解，并且求出解之間的間隔，那麼就可以求出模的線性方程的解集了.
我們設解之間的間隔為dx.那麼有a*x = b(mod n); a*(x+dx) = b(mod n);
兩式相減，得到: a*dx(mod n)= 0;
也就是說a*dx就是a的倍數，同時也是n的倍數，即a*dx是a 和 n的公倍數.為了求出dx,我們應該求出a 和 n的最小公倍數,此時對應的dx是最小的。
設a 和 n的最大公約數為d,那麼a 和 n 的最小公倍數為(a*n)/d. 即a*dx = a*n/d; 是以dx = n/d. 是以解之間的間隔就求出來了.
bool modular_linear_equation(int a,int b,int n)
{
int x,y,x0,i;
int d=exgcd(a,n,x,y);
if(b%d)
return false;
x0=x*(b/d)%n; //特解
for(i=1;i<d;i++)
printf("%d\n",(x0+i*(n/d))%n);
return true;
}
![【C素數】素數（質數）和分解質因數[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)