首页 > 代码库 > luogu P1362 兔子数 x

luogu P1362 兔子数 x

2024-10-17 20:28:02   202人阅读

 P1362 兔子数

题目描述

设 S(N ) 表示 N 的各位数字之和，如 S(484) = 4+8+4 = 16， S(22) = 2+2 = 4。如果一个正整数满足 S(x*x) = S(x) *S(x)，我们称之为 Rabbit N umber。比方说，22 就是一个 Rabbit N umber，因为 S(484) = S(22) *S(22)。

现在，给出一个区间 [L, R]，求在该区间内的 Rabbit N umber 的个数。

输入输出格式

输入格式：

 

输入仅一行，为空格隔开的两个数 L 和 R。

 

输出格式：

 

输出仅一行一个整数，表示所求 Rabbit N umber 的个数。

 

输入输出样例

输入样例#1：
样例1：22 22样例2：484 484样例3：1 58样例4：58 484样例5：1000000000 1000000000
输出样例#1：
样例1：1样例2：0样例3：12样例4：24样例5：1

说明

1 <= L <= R <= 10^9

思路:

　　1.首先看数据范围(1 <= L <= R <= 10^9),这说明最大的数S(a*a)一定会比18*9(162)要小(因为S是加和嘛~),所以S(a)就一定会比13要小,因为13*13=169(稍微>162),所以不可能会比13要大.

　　2.因为经过大量实(打)验(表)之后得出每一个兔子数的每一位上的数一定会<=3,因为如果某数字x的一位a>=4.那么它在该位的贡献是a^2的 但是在 x 中这一位自乘进了一位 故贡献为 a^2/10+a^2%10

　　3.那么这道题的思路就很明了了:

　　　　　　　　　　　　搜索+剪枝就好.

坑点:

　　要记得排次序,不能够直接输出cnt!!!

上代码:

#include <algorithm>#include <iostream>#include <cstring>#include <cstdio>#include <cmath>#define LL long longusing namespace std;int L,R,cnt,ANSWER;int ans[30000];void build(int x,int y,int z){     LL a=x;    a=a*a;    int b=0;    if(x>=L && x<=R)///在区间之内     {        while(a)        {            b+=a%10;            a/=10;        }        if(y*y==b)///寻找满足条件的数,并进行储存             ans[++cnt]=x;    }    ///停止的条件     if(z>R) return;    for(int i=0;i<4;i++)        build(x*10+i,y+i,z*10);}int main(){    scanf("%d%d",&L,&R);    build(0,0,1);    /*    for(int i=1;i<=cnt;i++)        printf("%d ",ans[i]);    printf("\n");    printf("--------------------------\n");    */    sort(ans+1,ans+1+cnt);    /*    for(int i=1;i<=cnt;i++)        printf("%d ",ans[i]);    printf("\n");    */    for(int i=1;i<=cnt;i++)    {        if(ans[i-1]!=ans[i])            ANSWER++;    }    printf("%d",ANSWER);    return 0;}

 

luogu P1362 兔子数 x


联系
我们