ACM数论模板及应用

引论

      数论是算法竞赛的宠儿，几乎每个算法竞赛（不论是ACM的省赛、区域赛还是牛客网上的网络赛）都会出一道关于数论的题。这很容易理解，因为算法与数学的关系极其密切，也可以说算法拼到最后就是在拼数学，所以学好数学对于我们来说是至关重要的。下面我将给出数论的基本模板并附上相关的习题及AC代码

模板

#include<stdio.h>
#include<math.h>
#include<string.h>

typedef long long LL;

const int maxn = 10000000 + 10;
const int maxp = 700000;

int vis[maxn];     //用于在埃氏筛法中判断是否访问过
int prime[maxp];    //用于存储素数

int fac[1000005];   //存储一个整数的素因子
int cnt = 0;     //记录有多少素因子

//因数分解
void factor(int n)
{
    int a = 1;
    for(int i=2; i*i<=n; i+=a,a=2)
    {
        if(n%i==0) while(n%i==0)
        {
            fac[cnt++] = i;
            n /= i;
        }
    }
    if(n > 1) fac[cnt++] = n;
}


//素性测试，用于判断单个数字是否是素数
int is_prime(LL n)
{
    if(n <= 1) return 0;
    LL m = floor(sqrt(n) + 0.5);
    for(LL i = 2; i <= m; i++)
        if(n % i == 0) return 0;
    return 1;
}


//筛选素数
void sieve(int n)
{
    int m = (int)sqrt(n + 0.5);
    memset(vis,0,sizeof(vis));
    for(int i = 2; i <= m; i++)
        for(int j = i * i; j <= n; j += i)
            vis[j] = 1;
}


//生成素数表，放在prime数组中，返回素数个数
int gen_primes(int n)
{
    sieve(n);
    int c = 0;
    for(int i = 2; i <= n; i++) if(!vis[i])
        prime[c++] = i;
    return c;
}


//欧几里得算法（又名辗转相除法）
LL gcd(LL a, LL b)
{
    return b == 0 ? a : gcd(b, a % b);
}


//扩展欧几里得算法
void gcdEx(LL a, LL b, LL &d, LL &x, LL &y)
{
    if(!b) { d = a; x = 1; y = 0; }
    else { gcdEx(b, a % b, d, y, x); y -= x * (a / b); }
}


//模运算
LL mul_mod(LL a, LL b, LL n)
{
    return a * b % n;
}


//快速幂+模运算
LL pow_mod(LL a, LL p, LL n)
{
    if(p == 0) return 1;
    if(p == 1) return a % n;


    LL ans = pow_mod(a, p / 2, n);
    ans = ans * ans % n;
    if(p & 1) ans = ans * a % n;
    return ans;
}


//计算单个欧拉函数
int euler_phi(int n)
{
    int m = (int)sqrt(n + 0.5);
    int 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[maxn];
void phi_table(int n)
{
    for(int i = 2; i <= n; i++) phi[i] = 0;
    phi[1] = 1;
    for(int i = 2; i <= n; i++)
        for(int j = i; j <= n; j += i){
            if(!phi[j]) phi[j] = j;
            phi[j] = phi[j] / i * (i - 1);
        }
}


//计算模n下a的逆
LL inv(LL a, LL n)
{
    LL d, x, y;
    gcdEx(a,n,d,x,y);
    return d == 1 ? (x + n) % n : -1;
}

应用

快速幂+模运算

hdu1061 hdu3003  hdu1163 hdu5690

欧拉函数

hdu1286   

素数

hdu2012 51nod1181 hdu2161

逆元

zoj3609

欧几里得算法及扩展欧几里得算法

uva11827 hdu2669  poj1061

习题代码

由于习题过多，在这里我不贴出我的代码，想看代码的同学可以参考我的github