EとFの難易度逆でしょ…。
http://codeforces.com/contest/758/problem/F
解法
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; } }
まとめ
競プロとは関係ないけど、ちょっと思い入れある算数?の問題と関係あったのでさっくり解けた。