kmjp's blog

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

Codeforces #392 Div2 F. Geometrical Progression

EとFの難易度逆でしょ…。
http://codeforces.com/contest/758/problem/F

問題

3整数N,L,Rが与えられる。
以下の条件を満たすN要素の整数列はいくつあるか。

  • 各要素は異なる値を持ち、等比数列を成す。
  • 各値は[L,R]に含まれる。

解法

N=1の場合は[L,R]の値ならすべて条件を満たすし、N=2の場合は[L,R]から異なる値を2つとれば条件を満たす。

以下N≧3の場合を考えよう。
以下数列が単調増加のケースのみ考えればよい。単調減少な数列は同数あるので、単調増加のケースを2倍すればよいだけである。

公比p=b/aとすると、全要素が整数であるためには初項がa^(N-1)の倍数でなければならない。
よってaを総当たりし、次にb>a(かつaとbは互いに素)を総当たりしよう。a,bがわかれば、あとは初項x*a^(N-1)、第N項x*b^(N-1)がともに[L,R]に含まれるようなxの数を求めるだけである。

ll N,L,R;


ll modpow(ll a, ll n) {
	ll r=1;
	while(n) {
		r=min(1LL<<30,r*((n%2)?a:1));
		a=min(1LL<<30,a*a);
		n>>=1;
	}
	return r;
}


void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>L>>R;
	if(N==1) {
		cout<<(R-L+1)<<endl;
	}
	else if(N==2) {
		cout<<(R-L+1)*(R-L)<<endl;
	}
	else if(N>=50) {
		cout<<0<<endl;
	}
	else {
		ll ret=0;
		ll bm=2;
		while(modpow(bm,N-1)<=R) bm++;
		
		for(ll a=1;a<=bm;a++) {
			ll ap=modpow(a,N-1);
			if(ap>R) break;
			for(ll b=a+1;b<=bm;b++) if(__gcd(a,b)==1) {
				ll bp=modpow(b,N-1);
				for(ll v=(L+ap-1)/ap*ap;v<=R;v+=ap) {
					if(v/ap*bp>R) break;
					ret++;
				}
			}
		}
		cout<<2*ret<<endl;
	}
}

まとめ

競プロとは関係ないけど、ちょっと思い入れある算数?の問題と関係あったのでさっくり解けた。