soj2704快速分解组合数.cpp

来自「一些ACM题目的解答,主要是soj和poj的」· C++ 代码 · 共 94 行

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

const int MAX = 1000001;

int a[MAX];

int next(int i)
{
    int j=i+1;
    while(a[j]==1&&j<MAX)
        j++;
    return j;
}
int primelist(void)
{
    int i,j,k;
    for(i=2;i*i<MAX;i=next(i))
    {
        for(j=i;j*i<MAX;j=next(j))
        {
            for(k=i*j;k<MAX;k*=i)
            {
                a[k]=1;
            }
        }
    }
    for(i=2,j=0;i<MAX;i++)
    {
        if(!a[i])
            a[j++]=i;
    }
    return j;
}

int main(void)
{
    int num = primelist();
    int t;
    scanf("%d",&t);
    while(t--)
    {
        int n,m,k;
        scanf("%d%d%d",&n,&m,&k);
        int i=0;
        i=0;
        int q=n-m;
        bool flag=true;
        int num1,num2,num3,numk;
        for(i=0;i<num;i++)
        {
            num1=num2=num3=numk=0;
            int temp=n;
            while(temp>0)
            {
                num1+=temp/a[i];
                temp/=a[i];
            }
            temp=m;
            while(temp>0)
            {
                num2+=temp/a[i];
                temp/=a[i];
            }
            temp=q;
            while(temp>0)
            {
                num3+=temp/a[i];
                temp/=a[i];
            }
            while(k%a[i]==0)
            {
                numk++;
                k/=a[i];
            }
            if(num1-num2-num3-numk<0)
            {
                flag=false;
                break;
            }
        }
        if(flag)
        {
            printf("Yes\n");
        }
        else
        {
            printf("No\n");
        }
    }
    return 0;
}