SCUT - 289 - 小O的数字

https://scut.online/p/289

一个水到飞起的模板数位dp。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

bool notp[2000];

const int MAXS1=200;

const int MAXS2=2000;

int a[20];

ll dp[20][MAXS1][MAXS2];

ll dfs(int pos,int s1,int s2,bool lead,bool limit) {

    if(pos==-1) {

        if(notp[s1]||notp[s2])

            return 0;

        else

            return 1;

    }

    if(!limit && !lead && dp[pos][s1][s2]!=-1)

        return dp[pos][s1][s2];

    int up=limit?a[pos]:9;

    ll ans=0;

    for(int i=0; i<=up; i++) {

        ans+=dfs(pos-1,s1+i,s2+i*i,lead && i==0,limit && i==a[pos]);

    }

    if(!limit && !lead)

        dp[pos][s1][s2]=ans;

    return ans;

}

ll solve(ll x) {

    if(x<=0)

        return 0;

    int pos=0;

    while(x) {

        a[pos++]=x%10;

        x/=10;

    }

    return dfs(pos-1,0,0,true,true);

}

int main() {

#ifdef Yinku

    freopen("Yinku.in","r",stdin);

#endif // Yinku

    memset(dp,-1,sizeof(dp));

    notp[0]=1;

    notp[1]=1;

    for(int i=2; i<2000; i++) {

        if(!notp[i]) {

            for(int j=i+i; j<2000; j+=i) {

                notp[j]=1;

            }

        }

    }

    int T;

    scanf("%d",&T);

    ll le,ri;

    while(T--) {

        scanf("%lld%lld",&le,&ri);

        printf("%lld\n",solve(ri)-solve(le-1));

    }

}

巴特西

SCUT - 289 - 小O的数字 - 数位dp

最新文章

热门文章