TopCoder SRM 466 Div1 Easy LotteryCheating

問題

番号のかかれたくじがある。（leading zeroがある場合がある）
このくじは、書かれた数が0または、約数の個数が奇数なら当たりである。

くじの番号を何桁か書き換えて当たりにしたい。
最小で何桁を変えなければならないか、求めよ。

制約条件

くじにかかれた数字の個数≦10

方針

約数の個数が奇数⇔平方数
10桁以下の平方数は、10^5個くらいと少ないので、
全部調べて、いちばん書き換える数が少ないのを求める。

leading zeroに注意する。

ソースコード

class LotteryCheating {
	public:
	int minimalChange(string ID) 
	{
		int n=ID.size(),ans=n;
		ll N=1;
		rep(i,n)N*=10;
		for(ll i=0;i*i<N;i++){
			char buf[20]="0000000000000000",buf2[20];
			sprintf(buf2,"%lld",i*i);
			strcpy(buf+n-strlen(buf2),buf2);
			int cnt=0;
			rep(j,n)if(buf[j]!=ID[j])cnt++;
			ans=min(ans,cnt);
		}
		return ans;
	}
};