数论总结与代码

一.素数打表：

1.平常打表：

for(i=2;i<=n;i++)    
        if(!s[i])    
        {    
            for(j=2*i;j<=n;j+=i)    
                s[j]=1;    
        } 

void get_prime()  
{  
    int cnt = 0;  
    for (int i = 2; i < N; i++)  
    {  
        if (!tag[i])  
            p[cnt++] = i;  
        for (int j = 0; j < cnt && p[j] * i < N; j++)  
        {  
            tag[i*p[j]] = 1;  
            if (i % p[j] == 0)  
                break;  
        }  
    }  
}  

1.欧几里得：

int gcd(int a,int b)
{
    return b==0?a:gcd(b,a%b);
}

//求整数x和y，使得ax+by=d，且|x|+|y|最小。其中d=gcd(a,b)
void extend_gcd(int a,int b,int &d,ll &x,ll &y)
{
    if(!b) d=a,x=1,y=0;
    else {extend_gcd(b,a%b,d,y,x);y-=x*(a/b);}
}

//求a^b%n
ll mod(ll a,ll b,int n)
{
    if(b==0) return 1;
    ll ans=mod(a,b/2,n);
    ans=ans*ans%n;
    if(b&1) ans=ans*a%n;
    return ans;
}

欧拉函数phi(n)等于不超过n且和n互素的整数个数。 互素：两个数的最大公约数为1的数称为互素数。

1.单个欧拉函数求法代码：

int euler_phi(int n)
{
    int m=sqrt(n+0.5),ans=n;
    for(int i=2;i<=m;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 phi[MM]
void phi_table(int n)
{
    mem(phi,0); phi[1]=1;
    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);
            }
}

五.乘法逆：

在n的同余类中的两个数a和b满足ab=1,比如在15的同余类中7*13=1，在这种情况下，说a和b互为乘法的逆。即7的逆的13，13的逆为7；如果知道a就可以求b，知道b也就可以求a。代码如下：

1.用扩展欧几里得求：

//计算模n下a的逆。如果不存在逆，返回-1
int inv(int a,int n)
{
    int d,x,y;
    extend_gcd(a,n,d,x,y); //扩展欧几里得函数
    return d==1?(x+n)%n:-1;
}

2.利用欧拉定理求：

//a的逆就是mod(a,n-2,n)
ll mod(ll a,ll n-2,int n)
{
    if(b==0) return 1;
    ll ans=mod(a,b/2,n);
    ans=ans*ans%n;
    if(b&1) ans=ans*a%n;
    return ans;
}

1.线性模方程：axob(mod n)

//返回0时不存在解，为1有解
int mod_gcd(int a,int b,int n)
{
    int x,y,d,x0,i;
    extend_gcd(a,n,d,x,y);
    if(b%d) return 0;
    x0=x*(b/d)%n;
    for(i=1;i<d;i++)
        printf("%d\n",(x0+i*(n/d))%n);
    return 1;
}

2.费马小定理：a^(p-1) ≡1（mod p）

费马小定理是数论中的一个重要定理，其内容为： 假如p是质数，且(a,p)=1，那么 a^(p-1) ≡1（mod p）。

即：假如p是质数，且a,p互质，那么a的(p-1)次方除以p的余数恒等于1。

3.中国剩余定理：xoai(mod mi)

如果线性模方程有多个，xoai(mod mi)该怎么做呢？这里就可以用中国剩余定理了。令M为所有mi的乘积，则在模M的剩余系下原方程组有唯一解。

//n个方程：x=a[i](mod m[i]) (0<=i<n)
ll china(int n,int *a,int *m)
{
    ll M=1,d,y,x=0;
    for(int i=0;i<n;i++)
        M*=m[i];
    for(int i=0;i<n;i++)
    {
        ll w=M/m[i];
        gcd(m[i],w,d,d,y);
        x=(x+y*w*a[i])%M;
    }
    return (x+M)%M;
}

利用欧拉定理求解模方程，当n为素数时，解模方程a^xob(mod n)。根据欧拉定理，只需检查x=0,1,2,……,n-1是不是解即可因为a^(n-1)o1(mod n),当x超过n-1时a^x就开始循环了。

//求解模方程a^xb(mod n)。n为素数。无解返回0
int log_mod(int a,int b,int n)
{
    int m,v,e=1,i;
    m=sqrt(n+0.5);
    v=inv(mod(a,m,n),n);
    map<int,int>x;
    x[1]=0;
    for(i=1;i<m;i++)
    {
        e=e*a%n;
        if(!x.count(e)) x[e]=i;
    }
    for(i=0;i<m;i++)
    {
        if(x.count(b)) return i*m+x[b];
        b=b*v%n;
    }
    return 0;
}

数论总结与代码,布布扣,bubuko.com

数论总结与代码

原文：http://blog.csdn.net/u011466175/article/details/20218021