OI数论总结

最近学习了一下数论，把总结的东西记下来吧。

从简单的开始吧

线性筛法：

#define maxn
void linear_test(int n){
    int not_prime[maxn], prime[maxn],prime_count = 0;
    memset(not_prime,0,sizeof(not_prime));
    not_prime[1] = 1;
    for(int i = 2;i <= n;i++){
        if(!not_prime[i]) prime[prime_count++] = i;
        for(int j = 0;j < prime_count;j++){
            if(prime[j] * i > n) break; 
            not_prime[prime[j] * i] = 1;
            if(i % prime[j] == 0) break;
            } 
        } 
}

这个算法的作用的结果是筛出了所有的素数，其副产品是得到了所有数的最小素因子。

高级一点

组合数求模，即求[tex]C^n_m \bmod p[/tex]

当[tex]m\le100000[/tex]且p为质数时，只需暴力求[tex]m![/tex]和[tex]\begin{matrix}\prod_{i=n-m+1}^n i\end{matrix}[/tex]即可

例题如fzu2020,代码如下

#include<cstdio>
int t,n,m,p;
int MultiMod(int a,int b,int p){//a*b % p
    int ret = 0,m = a;
    while(b){
        if(b & 1) ret = (ret + m) % p;
        m = (m + m) % p;
        b >>= 1;
        }
    return ret;
}     
int PowerMod(int a,int b,int p){//a^b % p
    int ret = 1,m = a;
    while(b){
        if(b & 1) ret = MultiMod(ret,m,p);
        m = MultiMod(m,m,p);
        b >>= 1;
        }
    return ret;
}
int main(){
    scanf("%d",&t);
    for(int i = 0;i<t;i++){
        scanf("%d%d%d",&n,&m,&p);
        int res = 1;
        for(int j = 1;j<=m;j++) res = MultiMod(res,j,p);
        res = PowerMod(res,p-2,p);
        for(int j = 0;j<m;j++) res = MultiMod(res,n-j,p);
        printf("%d\n",res);
        }
    return 0;
}

将n,m扩展至1000000000直接应用lucas定理[tex]C^n_m \bmod p \equiv \prod C^{a_i}_{b_i} \pmod{p}[/tex]，其中[tex]a_i,b_i[/tex]表示p进制下n和m的第i位。规定[tex]n>m \Rightarrow C^n_m = 0[/tex]。注意此题时限有些紧，把PowerMod中的MultiMod换为long long下的a*b%p即可加速很多。

#include<cstdio>
int t,n,m,p;
int MultiMod(int a,int b,int p){//a*b % p
    int ret = 0,m = a;
    while(b){
        if(b & 1) ret = (ret + m) % p;
        m = (m + m) % p;
        b >>= 1;
        }
    return ret;
}     
int PowerMod(int a,int b,int p){//a^b % p
    int ret = 1,m = a;
    while(b){
        if(b & 1) ret = (long long)ret*(long long)m%(long long)p;
        m = (long long)m*(long long)m%(long long)p;
        b >>= 1;
        }
    return ret;
}
int C(int n,int m,int p){
    if(n < m) return 0;
    if(m == 0 || n == m) return 1;
    int res = 1;
    for(int j = 1;j<=m;j++) res = (long long)res*(long long)j%(long long)p;
    res = PowerMod(res,p-2,p);
    for(int j = 0;j<m;j++) res = (long long)res*(long long)(n-j)%(long long)p;
    return res;
}
int lucas(int n,int m,int p){
    if(n < m) return 0;
    if(m == 0 || n == m) return 1;
    return MultiMod(C(n%p,m%p,p),lucas(n/p,m/p,p),p);
}    
int main(){
    scanf("%d",&t);
    for(int i = 0;i<t;i++){
        scanf("%d%d%d",&n,&m,&p);
        printf("%d\n",lucas(n+m,n,p));
        }
    return 0;
}

然后是hdu3398，使用组合数学经典的转化方法即可将其转化为求[tex]C^{m}_{n+m}-C^{m-1}_{n+m} \bmod 20100501[/tex]化简[tex]\frac{\(n+m\)!\(n-m+1\)}{m!\(n+1\)!} \bmod 20100501[/tex]，先使用前面介绍的线性筛法，然后再用阶乘统计素因数的简单方法，即对于素因数[tex]x[/tex]，若欲求得[tex]n![/tex]，只需算[tex]\sum_{x^i<=n} \lfloor\frac{n}{x^i}\rfloor[/tex]

#include<cstdio>
#include<cstring>
#define maxn 2000010
#define base 20100501
int t,not_prime[maxn],prime[maxn],prime_count = 0,np[maxn];
int MultiMod(int a,int b,int p){//a*b % p
    int ret = 0,m = a;
    while(b){
        if(b & 1) ret = (ret + m) % p;
        m = (m + m) % p;
        b >>= 1;
        }
    return ret;
}     
int PowerMod(int a,int b,int p){//a^b % p
    int ret = 1,m = a;
    while(b){
        if(b & 1) ret = (long long)ret*(long long)m%(long long)p;
        m = (long long)m*(long long)m%(long long)p;
        b >>= 1;
        }
    return ret;
}
void linear_test(int n){
    memset(not_prime,0,sizeof(not_prime));
    not_prime[1] = 1;
    for(int i = 2;i <= n;i++){
        if(!not_prime[i]) prime[prime_count++] = i;
        for(int j = 0;j < prime_count;j++){
            if(prime[j] * i > n) break; 
            not_prime[prime[j] * i]= 1;
            if(i % prime[j] == 0) break;
            } 
        } 
}
void factor(int n,int p){
    for(int i = 0;i<prime_count;i++){
        int t = 1;
        while(t <= n/prime[i]) t *= prime[i],np[i] += p*(n/t);
        }
}         
int main(){
    linear_test(maxn-1);
    scanf("%d",&t);
    while(t--){
        int n,m;
        int ret = 1;
        scanf("%d%d",&n,&m);
        memset(np,0,sizeof(np));
        factor(n+m,1);
        factor(m,-1);
        factor(n+1,-1);
        int f = n - m + 1;
        for(int i = 0;i<prime_count;i++) while(f % prime[i] == 0) np[i]++,f /= prime[i];
        for(int i = 0;i<prime_count;i++) if(np[i]) ret = MultiMod(ret,PowerMod(prime[i],np[i],base),base);
        printf("%d\n",ret);
        }
    return 0;
}

Baby Step Giant Step Algorithm:

第一次听这个算法觉得挺玄乎的，这次做sdoi2013 day1 random自己推了一下，感觉也不是很难的样子。简单来说，就是一个分块算法。简单描述一下：这个算法旨在求解这样一个关于x的方程[tex]a^x \equiv b \pmod{p}[/tex]。如果我们取一个长度为m的块，即将[tex]a^0,a^1...a^{m-1}[/tex]预处理出来，并放入一个hash表中，再枚举[tex]a^0,a^m,a^{2m}...a^{\left \lfloor \frac{p}{m} \right \rfloor * m}[/tex]，查找hash表，看是否存在某个值与枚举值相乘模p后等于b若存在则可很容易计算出x。容易发现此时时间复杂度为[tex]O(m+\frac{n}{m})  [/tex]在[tex]m = \sqrt{n}[/tex]时取得极值。此时时间复杂度为[tex]O(\sqrt{n})[/tex]。