soj3020多重集的排列问题.cpp

一些ACM题目的解答,主要是soj和poj的

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

const int MAX = 2<<20+1;

bool icon[MAX];

long prime[MAX];

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

int main(void)
{
    memset(icon,true,sizeof(icon));
    int len = primelist();
    int n;
    long long jie[21];
    jie[0]=1;
    for(n=1;n<21;n++)
        jie[n]=jie[n-1]*n;
    int factor[10000];
    while(scanf("%d",&n)!=EOF)
    {
if(icon[n])
{
printf("1 1\n");
continue;
}
        memset(factor,0,sizeof(factor));
        int n1=n;
        int i=0,max=0;
        int num=0;
        while(n1!=1)
        {    
            while(n1%prime[i]==0)
            {
                factor[num]++;
                n1/=prime[i];
            }
            if(n%prime[i]==0)
            {
                max+=factor[num];
                num++;
            }
            i++;
        }
        long long result=jie[max];
        for(i=0;i<num;i++)
        {
            if(factor[i]>1)
            {
                result/=jie[factor[i]];
            }
        }
        printf("%d %lld\n",max,result);
    }
    return 0;
}