bzoj4835 找規律+莫比烏斯反演

4833: [Lydsy2017年4月月賽]最小公倍佩爾數

Time Limit: 8 Sec   Memory Limit: 128 MB

Submit: 125   Solved: 57

[ Submit][ Status][ Discuss]

Description

 令(1+sqrt(2))^n=e(n)+f(n)*sqrt(2),其中e(n),f(n)都是整數，顯然有(1-sqrt(2))^n=e(n)-f(n)*sqrt(2)。令g(

n)表示f(1),f(2)…f(n)的最小公倍數，給定兩個正整數n和p,其中p是質數，并且保證f(1),f(2)…f(n)在模p意義 下均不為0,請計算sigma(i*g(i)),1<=i<=n.其在模p的值。

Input

第一行包含一個正整數 T ，表示有 T 組資料，滿足 T≤210 。接下來是測試資料。每組測試資料隻占一行，包含 兩個正整數 n 和 p ，滿足 1≤n≤10^6,2≤p≤10^9+7 。保證所有測試資料的 n 之和不超過 3×10^6  。

Output

對于每組測試資料，輸出一行一個非負整數，表示這組資料的答案。

Sample Input

5

1 233

2 233

3 233

4 233

5 233

Sample Output

1

5

35

42

121

首先根據給的兩個式子，可以算出f（n）,然後就可以找到規律，f(i)=f(i-1)*2+f(i-2)....然後就交給題解了。。。推出h（n），，然後得到g（n）。。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll f[1000010],g[1000010],p;
ll qpow(ll a,ll b)
{
    ll ans=1;
    while(b)
    {
        if(b&1) ans=(ans*a)%p;
        b>>=1; a=(a*a)%p;
    }return ans;
}
int main()
{
    int t;scanf("%d",&t);
    while(t--)
    {
        int n;scanf("%d%lld",&n,&p);f[1]=1;f[0]=0;
        for(int i=2;i<=n;i++){f[i]=(f[i-1]*2%p+f[i-2])%p;}
        for(int i=1;i<=n;i++)
        {
            ll inv=qpow(f[i],p-2);
            for(int j=i+i;j<=n;j+=i)
                f[j]=(f[j]*inv)%p;
        }
        ll lcm=1,ans=0;
        for(int i=1;i<=n;i++)
        {
            lcm=lcm*f[i]%p;
            ans=(ans+(lcm*i%p))%p;
        }
        printf("%lld\n",ans);
    }
    return 0;
}