SRM510 Div2 Hard(1000) TheLuckyBasesDivTwo

TheLuckyBasesDivTwo

B進数で表したときの桁数ごとに分けて考える。1桁の場合にLuckyとなるのはnが4か7のとき。この場合lucky baseは無数に存在する。2桁の場合は4*B+4=n, 4*B+7=n, 7*B+4=n, 7*B+7=nとなるようなBが存在するかを調べる。3桁以上となる場合、Bは√n未満なので全て調べる。

bool lucky( long long n, long long B )
{
    for ( ; n>0; n/=B )
        if ( n%B!=4 && n%B!=7 )
            return false;
    return true;
}

class TheLuckyBasesDivTwo{public:
long long find( long long n )
{
    //  1桁
    if ( n==4 || n==7 )
        return -1;

    //  2桁
    long long ans = 0;

    for ( int d1=4; d1<=7; d1+=3 )
    for ( int d2=4; d2<=7; d2+=3 )
    {
        long long B = (n-d1)/d2;
        if ( d1<B && d2<B && d2*B+d1==n )
            ans++;
    }

    //  3桁以上
    for ( long long B=2; B*B<=n; B++ )
        if ( lucky(n,B) )
            ans++;

    return ans;
}};