pongo英雄会-幸运数题解

显然我们只要知道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

巴特西

pongo英雄会-幸运数题解

最新文章

热门文章