SRM466 Div1 Easy(250), Div2 Medium(500) LotteryCheating

LotteryCheating

たいていの数nはある整数pが約数なら、n/pも約数となるので、偶数個の約数を持つ。約数が奇数個となるのはnが平方数の場合のみ。この時はp=√nでp=n/pとなる。
10桁以下の平方数は10⁵個しかない。

#include <string>
#include <cstdio>

using namespace std;

class LotteryCheating
{
    int diff( long long a, long long b, int d );
public:
    int minimalChange( string ID );
};

int LotteryCheating::minimalChange( string ID )
{
    long long id;
    sscanf( ID.c_str(), "%lld", &id );
    int d = (int)ID.size();

    int ans = d;

    long long lim=1;
    for ( int i=0; i<d; i++ )
        lim*=10;

    for ( long long i=0; i*i<lim; i++ )
        ans = min( ans, diff(id,i*i,d) );

    return ans;
}

//  aとbをd桁の数とみなして異なる箇所の個数を返す
int LotteryCheating::diff( long long a, long long b, int d )
{
    int c = 0;

    for ( int i=0; i<d; i++ )
    {
        if ( a % 10 != b % 10 )
            c++;
        a /= 10;
        b /= 10;
    }

    return c;
}