题目大意
求从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 = ;
for(int i = ; i <= n; i++) ans *= x;
return ans;
}
ll gcd(ll x, ll y) { return (x%y == ) ? y : gcd(y, x%y); }
ll n, l, r;
int main()
{
cin>>n>>l>>r;
if(n == ) cout<<r-l+;
else if(n == )
{
cout<<(r-l+)*(r-l);
}
else if(n > )
{
cout<<;
}
else
{
ll ans = ;
for(int i = ; i < r; i++)
{
int p = i, R = r/power(p, n-);
if(R == ) break;
for(int j = ; j < p; j++)
{
int q = j;
int L = (l-)/power(q, n-)+;
if(L > R) continue;
if(gcd(p, q) == ) { ans += (R-L+); }
}
}
cout<<ans*<<endl;
}
}