学步园

http://blog.csdn.net/acm_ted/article/details/8018440

题意：从l到r这r-l+1个数字中任意选取k个数字作为一个集合xi，对于每个集合xi，设yi为以xi集合中的数字为下标的斐波那契数的最大公约数，问max{yi}是多少，答案对m求余。

【注】

求max{gcd(fib(x1),fib(x2),...,fib(xk))} (l<=xi<=r)

题解：根据斐波那契最大公约数定理，gcd(fib(a),fib(b))=fib(gcd(a,b))，且斐波那契数列单调递增，则题目简化为求一个集合xi使得这个集合的最大公约数最大。设求解的最大公因数为idx,则idx满足r/idx-(l-1)/idx>=k，即在[l,r]范围内有k个以上idx的倍数，不断枚举idx即可。第idx个斐波那契数可以通过矩阵快速幂乘求解。

代码：

#include<cstdio>
#include<cstring>
#include<cmath>
#include<set>
#include<algorithm>
using namespace std;
#define LL long long
struct matrix
{
    LL b[2][2];
};
LL m;
matrix quickpow(matrix a,matrix b)//矩阵乘法
{
    matrix ret;
    for(int i=0; i<=1; ++i)
    {
        for(int j=0; j<=1; ++j)
        {
            ret.b[i][j]=0;
            for(int k=0; k<=1; ++k)
            {
                ret.b[i][j]=(ret.b[i][j]+(a.b[i][k]*b.b[k][j]))%m;
            }
        }
    }
    return ret;
}
LL check(LL n)//矩阵快速幂乘
{
    matrix a= {{{1,1},{1,0}}};
    matrix b= {{{1,0},{0,1}}};
    for(; n;)
    {
        if(n&1)
        {
            b=quickpow(a,b);
        }
        n=n>>1;
        a=quickpow(a,a);
    }
    return b.b[1][0];
}
int main()
{
    LL l,r,k,t;
    scanf("%I64d%I64d%I64d%I64d",&m,&l,&r,&k);
    LL idx=r/k;
    for(;idx>1;)
    {
        if(r/idx-(l-1)/idx>=k) break;
        idx=r/(r/idx+1);
    }
    printf("%I64d\n",check(idx));
    return 0;
}