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 = ;
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;
}
}
上一篇:Lucene 4.7 --高亮显示


下一篇:浅谈iptables防SYN Flood攻击和CC攻击