首页 > 代码库 > 洛谷 P1362 兔子数
洛谷 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
屠龙宝刀点击就送
经过2.9G打表发现
rabbit number的各位数字一定<=3
#include <cstdlib>#include <cstdio>#include <stack>#include <cmath>typedef long long LL;using namespace std;int maxn,L,R,l,d[200],i,ans;LL geth(LL f){ LL h=0; while(f) { h+=f%10; f/=10; } return h;}LL powe(LL a,LL b){ LL base=a,r=1; while(b) { if(b&1) r*=base; base*=base; b>>=1; } return r;}void get(LL &x){ x=0; for(i=1;i<=l;++i) x=x*10+d[l-i+1];}void wamn(){ LL n; get(n); if(n>R) { printf("%d",ans); exit(0); } LL m=powe(n,2); LL x=geth(n),y=geth(m); if(x*x==y) ans++; d[1]++; int k=1; while(d[k]>3) { d[k+1]+=1; d[k]=0; l=max(l,k+1); k++; } wamn();}int main(){ scanf("%d%d",&L,&R); stack<int>q; while(L) { d[++l]=L%10; L/=10; } wamn();}
洛谷 P1362 兔子数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。