C++

「数论」启发式思路——fac数组存大整数

关于——为什么要写这个

我们都用过杨辉三角递推式生成过杨辉三角,可是往往时间效率只能达到n<=5000,在学习完二项式定理之后得知一种新的直接递推第n行的杨辉三角数的公式

数组表达形式:line[n][x]=line[n][x-1]*(n-x+1)/x

终于可以O(n)求组合数了!

但是别高兴的太早,实测在不取模的情况下n=30就会爆int,而我们知道:

(a+b)mod n=((a mod n)+(b mod n))mod n

(a-b)mod n=((a mod n)-(b mod n))mod n

(a*b)mod n=((a mod n)*(b mod n))mod n

到了除法时就不能这么痛快了。不信你算(a/b)mod n=((a mod n)/(b mod n))mod n一定会GG。

那要怎么办?

只能对分子分母进行分解质因数各生成一个fac[sqrt(n)][2]表,用fac[i][0]表示质数表,fac[i][1]表示以fac[i][0]为底数的指数个数,就比如
$$
12=2\times 2\times 3=2^{2}+3^{1}
$$

2 3 5 7 11 13
2 1 0 0 0 0

这个表格就描述了数组fac的内容:

代码实现

void factor(){
    for(int i=2;i*i<=m;i++){
        if(m%i==0){
            fac[++num][0]=i;
            fac[num][1]=0;
            do{
                fac[num][1]++;
                m/=i;
            }while(m%i==0);
        }
    }
    if(m>1){
        fac[++num][0]=m;
        fac[num][1]=1;
    }
}

说明:m是被拆分的整数

BTW 关于gcd和lcm

gcd(a,b)和lcm(a,b)都可以拿上面的表格判断,例如:

num 2 3 5 7 11
120 3 1 1 0 0
30 1 1 1 0 0
gcd 1 1 1 0 0
lcm 3 1 1 0 0
can_devided true true true true true

能否整除can_devided判断标准为120的各个质因子指数均大于等于30的各个质因子指数

gcd为各个位置两者中较小的 lcm为各个位置两者中较大的

竞赛题目

UVa 1635

AC code:

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define N 100005
using namespace std;
int line[N],n,m,cnt,fac[100005][2],a[100005],c[100005],num;
void factor(){
    for(int i=2;i*i<=m;i++){
        if(m%i==0){
            fac[++num][0]=i;
            fac[num][1]=0;
            do{
                fac[num][1]++;
                m/=i;
            }while(m%i==0);
        }
    }
    if(m>1){
        fac[++num][0]=m;
        fac[num][1]=1;
    }
}
bool check(int n,int i){
    int x=n-i;
    int y=i;
    for(int i=1;i<=num;i++){
        int p=fac[i][0];
        while(x%p==0){
            x/=p;
            c[i]++;
        }
        while(y%p==0){
            y/=p;
            c[i]--;
        }
    }
    for(int i=1;i<=num;i++){
        if(c[i]<fac[i][1])
            return 0;
        return 1;
    }
}
int main(){
    while(cin>>n>>m){
        num=cnt=0;
        factor();
        memset(c,0,sizeof(0));
        for(int i=1;i<=n-1;i++){
            if(check(n,i))
                a[cnt++]=i+1;
        }
        cout<<cnt<<endl;
        for(int i=1;i<=cnt-1;i++)
            cout<<a[i]<<" ";
        cout<<a[cnt]<<endl;

    }
    return 0;
}
/*
//递推法
comb[0][0]=comb[1][0]=comb[1][1]=1;
for(int i=1;i<=k;i++) comb[i][0]=1;
for(int i=2;i<=k;i++){
    for(int j=1;j<=i;j++){
        comb[i][j]=((comb[i-1][j-1]%10007)+(comb[i-1]    [j]%10007))%10007;
    }
}
//二项式定理
void work(){
    line[0]=line[1]=1;
    for(int x=1;x<=n;x++){
        line[x]=line[x-1]*(n-x+1)/x;
    }
}

*/
分享到