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

传送门

题意：

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

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

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

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

1≤n≤106,2≤p≤109+7 1 ≤ n ≤ 10 6 , 2 ≤ p ≤ 10 9 + 7

Solution:

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

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

（证明我也不会）

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

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

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

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

则 g(n)=∏T∈Sf(gcd(T))(−1)|T|+1 g ( n ) = ∏ T ∈ S f ( g c d ( T ) ) ( − 1 ) | T | + 1

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

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

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

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

=∏ni=1h(d) = ∏ i = 1 n h ( 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);
    }
}