鏈接：https://www.lydsy.com/JudgeOnline/problem.php?id=4833

推推式子，可以得到f(n)=2*f(n-1)+f(n-2)
然后就可以按照這個來做了
基本都是一樣的

Upd2019.4.19

yy了一個新的寫法
新的東西

CODE:

#include<cstdio> #include<algorithm> #include<iostream> #include<cstring> using namespace std; typedef long long LL; const int N=3000005; int MOD; int f[N]; int add (int x,int y) {x=x+y;return x>=MOD?x-MOD:x;} int mul (int x,int y) {return (LL)x*y%MOD;} int Pow (int x,int y) {if (y==0) return 1;if (y==1) return x;int lalal=Pow(x,y>>1);lalal=mul(lalal,lalal);if (y&1) lalal=mul(lalal,x);return lalal; } int g[N]; void Init (int n) {f[0]=0;g[1]=f[1]=1;for (int u=2;u<=n;u++) g[u]=f[u]=add(add(f[u-1],f[u-1]),f[u-2]);for (int u=1;u<=n;u++){ int Inv=Pow(g[u],MOD-2);for (int i=u+u;i<=n;i+=u) g[i]=mul(g[i],Inv);} } int main() {int T;scanf("%d",&T);while (T--){int n;scanf("%d%d",&n,&MOD);Init(n);int lalal=1,ans=0;for (int u=1;u<=n;u++) {lalal=mul(lalal,g[u]);ans=add(ans,mul(lalal,u));}printf("%d\n",ans);}return 0; }

總結

以上是生活随笔為你收集整理的bzoj 4833: [Lydsy1704月赛]最小公倍佩尔数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。