题目:http://poj.org/problem?id=3421
记忆化搜索竟然水过去了。仔细一想时间可能有点不对,但还是水过去了。
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
using namespace std;
const int N=(<<)+;
int n;
ll a[N],f[N];
void find(int x)
{
if(a[x])return;
a[x]=;
for(ll i=;i*i<=x;i++)
if(x%i==)
{
find(i);find(x/i);
ll tmp=a[x];
a[x]=max(a[x],max(a[i],a[x/i])+);
if(a[x]!=tmp)f[x]=;
if(a[i]==a[x]-)f[x]+=f[i];
if(i!=x/i&&a[x/i]==a[x]-)f[x]+=f[x/i];//i!=x/i
}
if(!f[x])f[x]=;
}
int main()
{
while(scanf("%d",&n)==)
{
find(n);
printf("%lld %lld\n",a[n],f[n]);
}
return ;
}
然后发现是质因数分解。
可以理解成需要乘一个数才能进一步,为了走最长的,就是乘最小的,也就是一个质因数。
方案数就是一堆组合数相乘啦。不敢预处理,现求阶乘也没爆。
没错,仔细一想最多只有20个质因数,因为是log的。
#include<iostream>
#include<cstdio>
#include<cstring>
#define ll long long
const int N=(<<)+,M=;
int n,p[M],k[M],tot,sum;
ll ans;
ll C(int n,int m)
{
ll ret=;
for(int i=n-m+;i<=n;i++)ret*=i;
for(int i=;i<=m;i++)ret/=i;
return ret;
}
int main()
{
while(scanf("%d",&n)==)
{
ans=;sum=;tot=;
for(int i=;i*i<=n;i++)
if(n%i==)
{
p[++tot]=i;k[tot]=;
while(n%i==)n/=i,k[tot]++;
sum+=k[tot];
}
if(n>)p[++tot]=n,k[tot]=,sum++;
printf("%d ",sum);
for(int i=;i<=tot;i++)
{
ans*=C(sum,k[i]);sum-=k[i];
}
printf("%lld\n",ans);
}
return ;
}