首页 > 代码库 > Codeforces Round #392 (Div. 2) F. Geometrical Progression

Codeforces Round #392 (Div. 2) F. Geometrical Progression

原题地址:http://codeforces.com/contest/758/problem/F

 

F. Geometrical Progression

time limit per test

4 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

For given n, l and r find the number of distinct geometrical progression, each of which contains n distinct integers not less than l and not greater than r. In other words, for each progression the following must hold: l?≤?ai?≤?r and ai?≠?aj , where a1,?a2,?...,?an is the geometrical progression, 1?≤?i,?j?≤?n and i?≠?j.

Geometrical progression is a sequence of numbers a1,?a2,?...,?an where each term after first is found by multiplying the previous one by a fixed non-zero number d called the common ratio. Note that in our task d may be non-integer. For example in progression 4,?6,?9, common ratio is .

Two progressions a1,?a2,?...,?an and b1,?b2,?...,?bn are considered different, if there is such i (1?≤?i?≤?n) that ai?≠?bi.

Input

The first and the only line cotains three integers n, l and r (1?≤?n?≤?107,?1?≤?l?≤?r?≤?107).

Output

Print the integer K — is the answer to the problem.

Examples

Input

1 1 10

Output

10

Input

2 6 9

Output

12

Input

3 1 10

Output

8

Input

3 3 10

Output

2

Note

These are possible progressions for the first test of examples:

  • 1;
  • 2;
  • 3;
  • 4;
  • 5;
  • 6;
  • 7;
  • 8;
  • 9;
  • 10.

These are possible progressions for the second test of examples:

  • 6,?7;
  • 6,?8;
  • 6,?9;
  • 7,?6;
  • 7,?8;
  • 7,?9;
  • 8,?6;
  • 8,?7;
  • 8,?9;
  • 9,?6;
  • 9,?7;
  • 9,?8.

These are possible progressions for the third test of examples:

  • 1,?2,?4;
  • 1,?3,?9;
  • 2,?4,?8;
  • 4,?2,?1;
  • 4,?6,?9;
  • 8,?4,?2;
  • 9,?3,?1;
  • 9,?6,?4.

These are possible progressions for the fourth test of examples:

  • 4,?6,?9;
  • 9,?6,?4.

 

 

题意:给定 n, l and r ,求项数为n, 公比不为1,且数列每一项都属于[l,r]范围的不同的 等比数列 的个数。

题解:其实是先缩小范围然后直接枚举。

 

考虑数据范围1?≤?n?≤?107,?1?≤?l?≤?r?≤?10

设等比数列公比为d, d表示为 q/p,其中q或p为不同时等于1,且互质的正整数。

递增和递减数列的情况是成对出现的,即p和q互换。

所以不妨只考虑递增数列的情况,即公比d表示为q/p,其中pq互质,p为任意正整数,q>p,q为大于等于2的正整数。

则数列末项整除于qn-1 其中q>=2,2^24>10^7, n>=24时无解。

 

n=1时为结果为r-l+1, n=2时结果为(r-l+1)*(r-l),n>24时0.

n>=3&&n<24时,可以通过枚举出p和q的情况求解。

 

n>=3, 由于数列末项整除于qn-1 ,则qn-1 ≤?107,即枚举 p,q的上界是(1071/(n-1),当n=3时,这个值为3162,可以通过暴力枚举实现。

枚举p,q,

每找到一对(p,q)且gcd(p,q)==1

考虑数列末项  an= a1*qn-1/pn-1  ,

要满足 a1>=l, an<=r 的范围条件,若 l*qn-1/pn-1 >r 则不满足题意,continue;

l*qn-1/pn-1 <=r 则有满足[l,r]范围的等比数列

 

现在求[l,r]范围,公比为q/p,项数为n的等比数列的个数。

数列各项为 a1, a1*q/p ……a1*qn-1/qn-1qn-1pn-1  /pn-1 /pn-1 pn-1q/pq/pq/pn-1 ,等比数列的个数即为a1可能的值。

末项为moa1*qn-1/ pn-1  所以a1必整除于pn-1 ,即a1可能的值为 [l,r*pn-1/qn-1]范围内可被 pn-1整除的, 即 (r*pn-1/qn-1)/pn-1-l/pn-1

 

#include <bits/stdc++.h>
#define LL long long
using namespace std;

LL gcd(LL a, LL b){
    if(b==0) return a;
    else return gcd(b,a%b);
}

LL QuickPow(LL a, LL n){
    LL ret=1;
    while(n){
        if(n&1) ret*=a;
        a*=a;
        n>>=1;
    }
    return ret;
}

LL l,r,n;
LL ans;

int main()
{
    cin>>n>>l>>r;
    if(n>24){
        cout<<0;return 0;
    }
    if(n==1){
        cout<<r-l+1;return 0;
    }
    if(n==2){
        cout<<(r-l+1)*(r-l);return 0;
    }

    //n>=3&&n<24的情况
    LL upperlimit,pn,qn;
    //p,q的枚举上界
    upperlimit=pow(2,double(log2(1e7+50)/(n-1))); //注意精度
    for(LL p=1;p<=upperlimit;p++)
        for(LL q=p+1;q<=upperlimit;q++)
            if(gcd(p,q)==1)
            {
                qn=QuickPow(q,n-1);
                pn=QuickPow(p,n-1);
                if(l*qn/pn>r) continue;

                //a1可能的值 :[l,r*pn/qn]范围内可被 pn整除的正整数,
                ans+=(r*pn/qn)/pn-(l-1)/pn;
            }
       //递增数列递减数列成对出现,只考虑了递增数列
        cout<<ans*2;
        return 0;
}

 

 

a1*qn-1/qn-1qn-1pn-1  /pn-1 /pn-1 pn-1q/pq/pq/pn-1 qn-1/qn-1qn-1pn-1  /pn-1 /pn-1 pn-1q/pq/pq/pn的

Codeforces Round #392 (Div. 2) F. Geometrical Progression