これは割と簡単な問題。
http://community.topcoder.com/stat?c=problem_statement&pm=11466
問題
ある10進数の数Nが与えらえる。
この数をM進数で表したとき、各桁が4か7だけで構成されるようにしたい。
Mは何通りあるか。
解法
Nが4か7ならM>=8のすべての数で条件を満たす。
それ以外の場合を考える。
まず、NがM進数で3桁以上になるケースを考える。
この場合N>=M^2なはずなので、Mの選択肢はさほど多くないため、Mを総当たりで調べよう。
残りはM進数が2桁になる場合なので、M進数で44,47,74,77となるようなMがあるか調べればよい。
class TheLuckyBasesDivTwo { public: int okok(ll n,ll b) { while(n) { if(n%b!=4 && n%b!=7) return 0; n/=b; } return 1; } long long find(long long n) { ll ret=0; if(n<4) return 0; if(n==4 || n==7) return -1; for(ll b=5;b*b<=n;b++) ret += okok(n,b); if((n-4)%4==0 && (n-4)/4>4) ret++; if((n-7)%4==0 && (n-7)/4>7) ret++; if((n-4)%7==0 && (n-4)/7>4) ret++; if((n-7)%7==0 && (n-7)/7>7) ret++; return ret; } };
まとめ
今回はすんなりでした。コードも単純。