BZOJ4833: [Lydsy1704月赛]最小公倍佩尔数-数论

传送门

题意：

令 (1+2–√)n=e(n)+f(n)∗2–√ ,其中 e(n),f(n) 都是整数。

令 g(n) 表示 f(1),f(2)…f(n) 的最小公倍数.

给定两个正整数n和p,其中p是质数，并且保证 f(1),f(2)…f(n) 在模p意义下均不为0

请计算 ∑ni=1i∗g(i),1<=i<=n .其在模p的值。

1≤n≤106,2≤p≤109+7

Solution:

第一次见到还有这种解法的题orz

首先我们需要知道一个结论：
当a,b互质时，形如 f(n)=a∗f(n−1)+b∗f(n−2) 的式子具有性质 gcd(f(x),f(y))=f(gcd(x,y))

~~（证明我也不会）~~

关于lcm，我们知道 lcm(S)=∏T∈Sgcd(T)(−1)|T|+1

回到题目上来：观察可得 f(0)=0,f(1)=1,f(n)=2f(n−1)+f(n−2)

那么 g(n)=lcm(f({ 1,2,...,n}))

方便起见假设 S={ 1,2,...,n},S′={ 1,2,...,⌊nd⌋}

则 g(n)=∏T∈Sf(gcd(T))(−1)|T|+1

到了这里重头戏来了：构造h满足 f(n)=∏d|nh(d)

得到 g(n)=∏T∈S(∏d|gcd(T)h(d))(−1)|T|+1

=∏ni=1h(d)∑T∈S′(−1)|T|+1

=∏ni=1h(d)−∑⌊nd⌋i=1(−1)i∗Ci⌊nd⌋

=∏ni=1h(d)

问题就这样解决了…

这做法清奇啊QAQ

代码：

#include<cstdio>
#include<iostream>
using namespace std;
int T;
int n,a,b,mod,ans,tot,gt;
int h[1000010],f[1000010];
int fast_pow(int x,int a)
{
    int ans=1;
    for (;a;a>>=1,x=1ll*x*x%mod)
        if (a&1) ans=1ll*ans*x%mod;
    return ans;
}
int main()
{
    scanf("%d",&T);
    while (T--)
    {
        scanf("%d%d",&n,&mod);  
        f[0]=0;f[1]=1;h[1]=1;
        for (int i=2;i<=n;i++) h[i]=f[i]=(2ll*f[i-1]+f[i-2])%mod;
        for (int i=2;i<=n;i++)
        {
            int nw=fast_pow(h[i],mod-2);
            for (int j=i+i;j<=n;j+=i)  h[j]=1ll*h[j]*nw%mod;
        }
        int ans=0,sum=1;
        for (int i=1;i<=n;i++)
            sum=1ll*sum*h[i]%mod,ans=(1ll*ans+1ll*i*sum)%mod;
        printf("%d\n",ans);
    }
}