Codeforces Round #392 (Div. 2) F. Geometrical Progression 找规律快速幂 F. Geometrical Progression

链接：

给定 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/