SRM510 Div2 Hard(1000) 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; }};