分类：唯一分解定理

CSU, 唯一分解定理, 容斥原理

CSU 1803

| Mr.Winter Zhang

类型: 容斥,唯一分解定理
题目连接: :earth_americas:CSU-1803

题解: 由素分可以得到

2016=2*2*2*2*2*3*3*7 所以我们可以判断出 a 中有多少2016的因子,然后算出b中与a至少互补的因子个数,利用容斥原理计算出最后的结果.

github: :moon:1803.cpp

Code:

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<cmath>
using namespace std;
typedef long long LL;
LL arr[10][10][10];
LL a,b;
int main(){
    ///2016=2*2*2*2*2*3*3*7

    while(~scanf("%lld%lld",&a,&b)){
        memset(arr,0,sizeof(arr));
        for(int i=0;i<6;++i)
            for(int j=0;j<3;++j)
                for(int t=0;t<2;++t)
                    arr[i][j][t]=a/(int)(pow(2,i)*pow(3,j)*pow(7,t));
        LL ans=0;
        for(int i=0;i<6;++i)
            for(int j=0;j<3;++j)
                for(int t=0;t<2;++t)
                    ans+=(arr[i][j][t]-arr[i+1][j][t]-arr[i][j+1][t]-arr[i][j][t+1]+arr[i+1][j+1][t]+arr[i+1][j][t+1]+arr[i][j+1][t+1]-arr[i+1][j+1][t+1])*(b/(int)(pow(2,5-i)*pow(3,2-j)*pow(7,1-t)));
        printf("%lld\n",ans);
    }
    return 0;
}
UVa, 二项式定理, 唯一分解定理, 数论, 组合数学

UVa 1635

| Mr.Winter Zhang

【类型】

唯一分解定理,二项式定理(组合数学)

【题目来源】

算法竞赛入门经典P320 例题10-6

UVa-1635-Irrelevant Elements

【Tip】

二项式定理展开式:C(n,k)=C(n,k-1)*(n-k+1)/k.

即 C[i]=C[i-1]*(n-i+1)/i.

注意,应该先乘再除,因为C[i-1]/i可能不是整数.但结果一定是整数.而且,因为二项式是递归乘法,所以有时可能会溢出long long,这题就是个例子.

【思路】

因为C(n,i)可能会爆long long,所以先对m做唯一分解，分解成若干素数,并记录每个素数的指数.然后以此计算m的唯一分解式中哥哥素因子在C(n-1,i-1)中的指数即可完成判断.这些指数依然可以用上面那个递推式递推,并且不会涉及高精度.

【参考】

Hengjie Yang

【Code】

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
using namespace std;
typedef long long LL;
LL C[100005];
int prime[101][2];
int fac_c[100];
int N,M;

int initM(int m){
    int primenum=0;
    for(int i=2;i<=sqrt(m);++i){
        if(m%i==0){
            prime[++primenum][0]=i;
            prime[primenum][1]=0;
            while(m%i==0){
                prime[primenum][1]++;
                m/=i;
            }
        }
    }
    if(m>1){
        prime[++primenum][0]=m;
        prime[primenum][1]=1;
    }
    return primenum;
}

bool check(int m,int k,int primenum){
    int a=m-k;
    int b=k;
    for(int i=1;i<=primenum;++i){
        for(;a%prime[i][0]==0;a/=prime[i][0],fac_c[i]++);
        for(;b%prime[i][0]==0;b/=prime[i][0],fac_c[i]--);
    }
    for(int i=1;i<=primenum;++i)
        if(prime[i][1]>fac_c[i])
        return false;
    return true;
}

int main(){
    while(cin>>N>>M){
        int primenum=initM(M);//唯一分解M,防止爆LL
        memset(fac_c,0,sizeof(fac_c));
        int cnt=0;//无关数个数
        for(int i=1;i<N;++i){
            //0~(n-1),这个是组合数C(m,n)的n.  m=n-1 index=i+1
            if(check(N,i,primenum))
                C[cnt++]=i+1;
        }
        printf("%d\n",cnt);
        for(int i=0;i<cnt;++i)
            printf(i==(cnt-1)?"%d\n":"%d ",C[i]);
    }
    return 0;
}
UVa, 唯一分解定理, 数论

UVa 10791

| Mr.Winter Zhang

【类型】

唯一分解定理,约数判断,分解质因数

【题目来源】

UVa-10791-Minimum Sum LCM

【Tip】

一开始一直TLE,后来发现需要优化成用小于等于√N 的质数来求N的因子(并非一定是质因子),最后剩下一个约分过后的N,如果N>1,则将N作为最后一个因子(一定是素数)加到最后的结果中.

其过程等同于素数筛法,先筛2^a1,再筛3^a2 …其筛出的ai不为0的因子的底数一定是素数.因为  *唯一分解定理:一个数可以分解为若干素数的幂相乘的形式.

【Code】

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;
typedef long long LL;

int main(){
    ios::sync_with_stdio(false);
    LL N;
    int lam=1;
    while(cin>>N){
        if(N<=0)break;
        LL sum=0,cnt=0;
        for(int i=2;i<=sqrt(N);++i){
            if(N%i==0){
                LL mut=1;
                cnt++;
                while(N%i==0){
                    N/=i;
                    mut*=i;
                }
                sum+=mut;
            }
        }
        if(N>1 || cnt==0){
            //这里的N是计算以后偶剩下的N,这个N一定是一个素数,直接加即可
            sum+=N;
            cnt++;
        }
        if(cnt==1) sum++;
       printf("Case %d: %lld\n",lam++,sum);
    }
    return 0;
}
UVa, 唯一分解定理, 数论

UVa 10375

| Mr.Winter Zhang

【类型】

唯一分解定理,素数筛法

【题目来源】

UVa-10375-Choose and divide

【唯一分解定理】

任何一个大于1的自然数N,如果N不为质数(素数)，那么N可以唯一分解成有限个质数的乘积N=P1a1P2a2P3a3……Pnan，这里P1<P2<P3……<Pn均为素数，其中指数ai是正整数。这样的分解称为N的标准分解式.

【思路】

根据题意得: 给定p q r s 求 ①.(p!s!(r-s)!)/(r!q!(p-q)!)

暴力会炸,至于为啥.

10000! 总位数：35660位,要不要试试？

1.先筛10000以内的素数.

2.数组e表示当前结果的唯一分解式中各个素数的指数,prime数组第i位的指数是多少.如:e={1，0，2，0，0，0 …}表示pow(2,1)*pow(5,2)=50

【Code】

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#include<cmath>
#define MAXN 10000
using namespace std;

int prime[MAXN];
bool is_prime[MAXN];
int primesize=0,p,q,r,s;

int e[MAXN];

void sieve(){
    memset(is_prime,1,sizeof(is_prime));
    is_prime[1]=is_prime[0]=false;
    for(int i=0;i<MAXN;++i){
        if(is_prime[i]){
            prime[primesize++]=i;
            for(int j=i*2;j<MAXN;j+=i)
                is_prime[j]=false;
        }
    }
}

//乘以或除以n,d=1表示乘,d=-1表示除
void add_integer(int n,int d){
    for(int i=0;i<primesize;++i){
        while(n%prime[i]==0){//必须是while
            n/=prime[i];
            e[i]+=d;
        }
        if(n==1)break;//提前终止循环,节约时间
    }
}

void add_factorial(int n,int d){
    for(int i=1;i<=n;++i)
        add_integer(i,d);
}

int main(){
    sieve();
    while(cin>>p>>q>>r>>s){
        memset(e,0,sizeof(e));
        //以下一串表示上面的公式①的分子和分母.
        add_factorial(p,1);
        add_factorial(s,1);
        add_factorial(r-s,1);
        add_factorial(q,-1);
        add_factorial(r,-1);
        add_factorial(p-q,-1);
        double ans=1;
        for(int i=0;i<primesize;++i)
            ans*=pow(prime[i],e[i]);
        printf("%.5lf\n",ans);
    }
    return 0;
}