TopCoder SRM 473 Div 2 Hard ChildlessNumbers

問題概要

整数nに対して、各桁の和D(n)がnを割り切るとき、n/D(n)を「nの親」と呼ぶ。
与えられた2数A,Bに対しこの間（境界含む）で、いかなる数の親にもなっていない数の個数を求めよ。

A≦B≦10^9, B-A≦10000を満たす。

解法

Xが子になるような数Yの候補の大きさを制限できないか考える。
Yが一番小さくなるのはD(Y)が1のときで、X≦Y,
Yが一番大きくなるのはYの数字が全て9のときで、Y≦(桁数)*9*Xであるので、
Yの候補としてX*200くらいまでを調べれば十分なことがわかる。

調べ方は総当りで200万通りしかないので総当りでよい。

ソースコード

ll cld(ll a)
{
	int s=0;
	for(ll b=a;b;b/=10)s+=b%10;
	if(a%s)return -1;
	return a/s;
}
bool ok(ll x)
{
	for(ll a=x;a<=200*x;a+=x)
	if(cld(a)==x)return 1;
	return 0;
}

class ChildlessNumbers {
	public:
	int howMany(int A, int B) 
	{
		int ans=0;
		for(int i=A;i<=B;i++)if(!ok(i))ans++;
		return ans;
	}
};