POJ 1775 Sum of Factorials 数论,基础题

时间:2023-01-28 13:18:02

输入一个小于1000000的正整数,是否能表达成式子:a1!+a2!+a3!+...+an (a1~an互不相等)。

因为10!>1000000,所以先打1~10的阶乘表。从a[10]开始递减判断。(a[0]=0!=1)

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std; int main()
{
//freopen("in.txt","r",stdin);
int n;
int a[11];
memset(a,0,sizeof(a));
a[0]=a[1]=1;
for(int i=2; i<=10; i++)
a[i]=i*a[i-1];
while(scanf("%d",&n))
{
if(n<0)
break;
bool flag=true;
if(n!=0)
for(int i=10; i>0; i--)
{
if(n<=a[i] && n>=a[i-1])
n-=a[i-1];
if(n==0)
{
flag=false;
break;
}
}
if(flag)
printf("NO\n");
else
printf("YES\n");
}
return 0;
}