SRM 484 DIV1 Easy - RabbitNumber (復習×)

問題


http://community.topcoder.com/stat?c=problem_statement&pm=11131&rd=14237

ある数xの平方数yを考えたとき、(x*x=y),
かつnの各桁の和で表わされるS(n)について、S(x)*S(x)=S(y)が成り立つとき
その数はRabbit Numberになる。

このとき、lowからhighまでの間のRabbit Numberの数を求める。
 

解き方


普通に解くとlow,highともに10^9であるため解くことができない。
そのため法則がないか考える。

ここで、xの各桁の数が3以下であればRabbit Numberになる可能性がある。
1*1=1,S(1)*S(1)=1
2*2=4,S(2)*S(2)=4
3*3=9,S(3)*S(3)=9 

しかし、4以上のとき、つまり桁上がりしてしまうときは決してRabbit Numberにならない。
4*4=16,S(4)*S(4)=16 (≠7) 
5*5=25,S(5)*S(5)=25 (≠7)

つまり、各桁が0~3の全ての数のうち、
平方数のS(n)とイコールになるものについて(この中でも2ケタ以上の数では桁上がりは発生しうるので)、lowとhighの間の数をカウントしてあげればよい。
 

コード


class RabbitNumber {

public:

int S(long long x){
int ret=0;
while(x>0){
ret+=x%10;
x/=10;
}
return ret;
}

int calc(int low,int high,int cur){
int ret=0;

FORE(i,0,4){
int x=10*cur+i;
if(x==0||S(x)*S(x)!=S((long long)x*x))continue;
if(low<=x&&x<=high)ret++;
if(x<=high/10)ret+=calc(low,high,x);
}

return ret;
}

int theCount(int low, int high) {
return calc(low,high,0);
}

};

using namespace std;

#define all(c) (c).begin(),(c).end()
#define FORE(i,d,e) for(int i=d;i<e;i++)
#define FOR(i,s,e) for (int i = int(s); i != int(e); i++)
#define FORIT(i,c) for (typeof((c).begin()) i = (c).begin(); i != (c).end(); i++)
#define ISEQ(c) (c).begin(), (c).end()

class RabbitNumber {

public:

bool ispossible(long long a){
long long b=a*a;

int ans1=0,ans2=0;
while(a>0)ans1+=(a%10),a/=10;
while(b>0)ans2+=(b%10),b/=10;

return ans1*ans1==ans2;
}

int rec(long long x,int low,int high){
int ret=0;
if(x<=high){
if(x!=0)ret+=rec(x*10,low,high);
ret+=rec(x*10+1,low,high);
ret+=rec(x*10+2,low,high);
ret+=rec(x*10+3,low,high);
if(low<=x && ispossible(x))ret++;
}
return ret;
}


int theCount(int low, int high) {
return rec(0,low,high);
}

};
このエントリーをはてなブックマークに追加