TopCoder SRM 540 Div2 Hard FractionInDifferentBases

これは割とすんなり解けた。
http://community.topcoder.com/stat?c=problem_statement&pm=11135

問題

有理数P/Qが与えられる。
これをX進数で表したとき無限小数となるようなXは、A<=X<=Bの間に何個あるか答えよ。

解法

まず、P/Qを約分してしまおう。1/Qが無限小数ならP/Qも無限小数なので、以後はQだけ考慮すればよい。

無限小数となるケースそのものではなく、無限小数とならないケースを除くことで答える。
有限小数となるケースは、XがQを構成する素因数をそれぞれ1個以上持って入れればよい。

よって、Qを素因数分解し、各素因数を1つずつだけ持つようなXを求める。
後はA～BのうちXの倍数は有限小数となるので、Xの倍数を除けばよい。

int NP,prime[100000];
const int prime_max = 1000000;
void cprime() {
	static int p[prime_max];
	int i,j;
	for(i=2;i<prime_max;i++) {
		if(p[i]) continue;
		prime[NP++]=i;
		for(j=i*2;j<prime_max;j+=i) p[j]=i;
	}
}
int nf[100001];

class FractionInDifferentBases {
	public:
	long long getNumberOfGoodBases(long long P, long long Q, long long A, long long B) {
		if(P==0) return 0;
		
		NP=0;
		cprime();
		
		ll g=__gcd(P,Q);
		P/=g;
		Q/=g;
		
		int i;
		ll pr=1;
		ZERO(nf);
		FOR(i,NP) {
			while((Q%prime[i])==0) nf[i]++,Q/=prime[i];
			if(nf[i]) pr*= prime[i];
		}
		pr*=Q;
		if(Q>1) prime[NP++] = Q,nf[NP-1]++;
		
		return (B-B/pr)-((A-1)-(A-1)/pr);
	}
};

まとめ

無限小数がテーマの問題は割と珍しいな。
以前1回だけあったことあったかな。