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 ≤ a_i ≤ r and a_i ≠ a_j , where a₁, a₂, ..., a_n is the geometrical progression, 1 ≤ i, j ≤ n and i ≠ j.

Geometrical progression is a sequence of numbers a₁, a₂, ..., a_n 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 a₁, a₂, ..., a_n and b₁, b₂, ..., b_n are considered different, if there is such i (1 ≤ i ≤ n) that a_i ≠ b_i.

Input

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

Output

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

Examples

Input

1 1 10

Output

Input

2 6 9

Output

Input

3 1 10

Output

Input

3 3 10

Output

Note

These are possible progressions for the first test of examples:

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 ≤ 10⁷, 1 ≤ l ≤ r ≤ 10⁷

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

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

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

则数列末项整除于q^n-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, 由于数列末项整除于q^n-1 ,则q^n-1 ≤ 10^7，即枚举 p,q的上界是（10⁷）^1/(n-1)，当n=3时，这个值为3162，可以通过暴力枚举实现。

枚举p,q，

每找到一对（p,q）且gcd（p,q）==1

考虑数列末项 an= a1*q^n-1/p^{n-1 ，}

要满足 a1>=l, an<=r 的范围条件，若 l*q^n-1/p^n-1 >r 则不满足题意，continue；

若 l*q^n-1/p^n-1 <=r 则有满足[l,r]范围的等比数列

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

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

末项为moa1*q^n-1/ p^n-1所以a1必整除于p^n-1 ，即a1可能的值为 [l,r*p^n-1/q^n-1]范围内可被 p^n-1整除的, 即（r*p^n-1/q^n-1)/p^n-1-l/p^n-1个

#include <bits/stdc++.h>

#define LL long long

using namespace std;

LL gcd(LL a, LL b){

    if(b==) return a;

    else return gcd(b,a%b);

}

LL QuickPow(LL a, LL n){

    LL ret=;

    while(n){

        if(n&) ret*=a;

        a*=a;

        n>>=;

    }

    return ret;

}

LL l,r,n;

LL ans;

int main()

{

    cin>>n>>l>>r;

    if(n>){

        cout<<;return ;

    }

    if(n==){

        cout<<r-l+;return ;

    }

    if(n==){

        cout<<(r-l+)*(r-l);return ;

    }

    //n>=3&&n<24的情况

    LL upperlimit,pn,qn;

    //p,q的枚举上界

    upperlimit=pow(,double(log2(1e7+)/(n-))); //注意精度

    for(LL p=;p<=upperlimit;p++)

        for(LL q=p+;q<=upperlimit;q++)

            if(gcd(p,q)==)

            {

                qn=QuickPow(q,n-);

                pn=QuickPow(p,n-);

                if(l*qn/pn>r) continue;

                //a1可能的值 :[l,r*pn/qn]范围内可被 pn整除的正整数,

                ans+=(r*pn/qn)/pn-(l-)/pn;

            }

       //递增数列递减数列成对出现，只考虑了递增数列

        cout<<ans*;

        return ;

}

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

巴特西

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

最新文章

热门文章