LEM6 - BIRTHDAY

Tác giả: hieult

Ngôn ngữ: C++

#include<iostream>
#define base 1000000000
#define nm 1001
//#include <conio.h>
using namespace std;
int tren[nm];
int duoi[nm];
long long kq[nm];
int b[nm];
int t=nm-1;
int n,m;
long long power(int x,int y)
{
     if (y==0)return 1;
     long long u=power(x,y/2);
     if (y%2==0)return u*u;
     return u*u*x;
}
void process(int a[],int n)
{
     for (int i=2;i*i<=n;i++)
     {
         if (n%i==0)
            for (int p=1;n%i==0;p++)
            {
                n/=i;
                a[i]++;
            }
     }
     if (n>1)
     a[n]++;
}
void mul(long long k,int&t)
{
     long long temp,nho=0;
     for (int i=1000;i>=t;i--)
     {
         temp=kq[i]*k+nho;
         kq[i]=temp%base;
         nho=temp/base;
     }
     while (nho>0)
     {
           t--;
           kq[t]=nho%base;
           nho=nho/base;
     }
}
int main()
{
    scanf ("%d%d",&n,&m);
    for (int i=0;i<m;i++)
    {
        scanf ("%d",&b[i]);
        n = n-b[i];
    }
    n++;
    if (n<m)
    {
       printf ("0");
       return 0;
    }
    for (int i=n;i>m;i--)
        process(tren,i);
    for (int i=n-m;i>=2;i--)
        process(duoi,i);
    kq[1000]=1;
    for (int i=1000;i>=2;i--)
    {
        tren[i]-=duoi[i];
        if (tren[i])
        {
           long long k=power(i,tren[i]);
           mul(k,t);
        }
    }
    printf ("%lld",kq[t]);
    for (int i=t+1;i<=1000;i++)
        printf("%09lld",kq[i]);
      //  getch();
    //return 0;
}

Download