Codeforces Round #392(Div 2) 758F（数论）
题目大意
求从l到r的整数中长度为n的等比数列个数，公比可以为分数
首先n=1的时候，直接输出r-l+1即可
n=2的时候，就是C(n, 2)*2
考虑n>2的情况
不妨设公比为p/q(p和q互素->既约分数)
那么等比数列为
k k*p/q k*(p/q)^2 ..... k*(p/q)^(n-1)
因为都是整数，所以k一定可以表示为x*q^(n-1)，化简数列得
x*q^(n-1) ........ x*p^(n-1)
也就是说，假如q < p, 那么最小值就是x*q^(n-1), 最大值就是x*p^(n-1)
接下来我们又发现当n>2的时候
p和q都必须小于等于sqrt(r) （因为p^2,q^2都小于等于r)
所以就直接从1到sqrt(r)枚举p和q即可，利用辗转相除判断互素，求出所有可行的x，这样复杂度就是rlog(r)
注意当n>30的时候，显然不存在任何等比数列，所以输出0即可(这样可以不用写快速幂，因为n很小)
#include <iostream> #include <cstdio> using namespace std; typedef long long ll; ll power(ll x, ll n) { ll ans = 1; for(int i = 1; i <= n; i++) ans *= x; return ans; } ll gcd(ll x, ll y) { return (x%y == 0) ? y : gcd(y, x%y); } ll n, l, r; int main() { cin>>n>>l>>r; if(n == 1) cout<<r-l+1; else if(n == 2) { cout<<(r-l+1)*(r-l); } else if(n > 30) { cout<<0; } else { ll ans = 0; for(int i = 2; i < r; i++) { int p = i, R = r/power(p, n-1); if(R == 0) break; for(int j = 1; j < p; j++) { int q = j; int L = (l-1)/power(q, n-1)+1; if(L > R) continue; if(gcd(p, q) == 1) { ans += (R-L+1); } } } cout<<ans*2<<endl; } }优质内容筛选与推荐>>
1、jdk环境变量配置
2、玩转HTML5移动页面（动效篇）
3、固定背景图片铺满浏览器窗口
4、input 中设置只能是数字
5、python 的os.getenv("PATH")和os.environ.get("PATH")的区别