kmjp's blog

競技プログラミング参加記です

TopCoder SRM 510 Div2 Hard TheLuckyBasesDivTwo

これは割と簡単な問題。
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;
	}
};

まとめ

今回はすんなりでした。コードも単純。