显然我们只要知道1~x范围有多少幸运数（用f(x)表示），lucky(x,y)=f(y)-f(x-1).
解法1. 计算排列数
由于y<=1000000000这个规模，我们不能暴力验证每个数是否是幸运数。可以想到，对于同样的数字组成，不同的数字排列对应不同的幸运数，比如12,21。那么就只需枚举合法的数字组成，算出相应的排列数。设数字i有a[i]个，n=Σa[i]，则对应的排列数是n!/∏a[i]!。
接下来就只要枚举那些合法的数字组成了。我们希望枚举时对每位的可取数字是没有限制的，可以分类来进行。下面举例说明。
比如x=2345. 当千位是0或1时，后三位是没有限制的，0~9都可以，可以用递归来枚举a[i]，然后结合已确定的千位来判断这种组成是否是幸运数，是的话答案就加上相应的排列数。
当千位等于2时，继续依次固定百位=0,1,2计算。余此类推。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<time.h>
using namespace std;
bool isPrime(int n)
{
if(n<2) return false;
int i;
for(i=2;i*i<=n;i++) if(n%i==0) return false;
return true;
}
bool check(int cnt[],int n1,int n2)
{
int i;
int s1=n1,s2=n2;
for(i=1;i<10;i++)
{
s1+=i*cnt[i];
s2+=i*i*cnt[i];
}
return isPrime(s1)&&isPrime(s2);
}
int fac[10];
void comFactorial()
{
int i;
fac[0]=1;
for(i=1;i<10;i++) fac[i]=fac[i-1]*i;
}
int nPermutation(int cnt[])
{
int i;
int n=0;
for(i=0;i<10;i++) n+=cnt[i];
int ans=fac[n];
for(i=0;i<10;i++) ans/=fac[cnt[i]];
return ans;
}
void dfs(int digit,int n,int cnt[],int n1,int n2,int &ans)
{
int i;
if(digit==10)
{
cnt[0]=n;
if(check(cnt,n1,n2))
ans+=nPermutation(cnt);
return ;
}
for(i=0;i<=n;i++)
{
cnt[digit]=i;
dfs(digit+1,n-i,cnt,n1,n2,ans);
}
}
int com(int x)
{
comFactorial();
int digit[12];
int cnt[12];
int i,j,n=0;
while(x>0)
{
digit[n++]=x%10;
x/=10;
}
int n1=0,n2=0,s1,s2,ans=0;
for(i=n-1;i>0;i--)
{
for(j=0;j<digit[i];j++)
{
s1=n1+j;
s2=n2+j*j;
dfs(1,i,cnt,s1,s2,ans);
}
n1+=digit[i];
n2+=digit[i]*digit[i];
}
for(i=0;i<=digit[0];i++)
{
s1=n1+i;
s2=n2+i*i;
if(isPrime(s1)&&isPrime(s2)) ans++;
}
return ans;
}
int lucky(int x,int y)
{
return com(y)-com(x-1);
}
解法2. dp
dp[n][s1][s2]表示n位，各位数字的和为s1,平方和为s2的方法数。根据第一位的数字来状态转移，dp[n][s1][s2]=Σdp[n-1][s1-i][s2-i*i] i=0...9
两种方法的共同之处是都要逐渐固定高位来分类计算。
#include <cstring>
#include <vector>
#include <iostream>
#include <set>
#include <map>
#include <algorithm>
#include<deque>
#include<cstdio>
#include<time.h>
using namespace std;
int dp[12][82][730];
bool isPrime(int n)
{
int i;
if(n<2) return false;
for(i=2;i*i<=n;i++) if(n%i==0) return false;
return true;
}
int f(int n,int s1,int s2)
{
if(dp[n][s1][s2]!=-1) return dp[n][s1][s2];
if(n==1)
{
if(s1<10&&s1*s1==s2) return dp[n][s1][s2]=1;
else return dp[n][s1][s2]=0;
}
else
{
int i;
int ans=0;
for(i=0;i<10&&i<=s1&&i*i<=s2;i++) ans+=f(n-1,s1-i,s2-i*i);
return dp[n][s1][s2]=ans;
}
}
int com(int x)
{
int a[20];
int num=0;
while(x>0)
{
a[num++]=x%10;
x/=10;
}
int ans=0;
int i,j,k,m;
int s1=0,s2=0;
int p1=0,p2=0;
for(k=num-1;k>0;k--)
{
for(m=0;m<a[k];m++)
{
s1=p1+m;
s2=p2+m*m;
for(i=0;i<=9*k;i++)
for(j=i;j<=81*k;j++)
{
if(isPrime(i+s1)&&isPrime(j+s2))
ans+=f(k,i,j);
}
}
p1+=a[k];
p2+=a[k]*a[k];
}
for(i=0;i<=a[0];i++)
if(isPrime(p1+i)&&isPrime(i*i+p2)) ans++;
return ans;
}
int lucky(int x,int y)
{
memset(dp,-1,sizeof(dp));
return com(y)-com(x-1);
}
转自 http://blog.csdn.net/shuyechengying/article/details/9164517