51nod1355：斐波那契的最小公倍数（数论）

题面
题意给出n个a&＃xff0c;问LCM{ f(a) }&＃xff0c;f为斐波那契数。

知乎靠谱的题解

记住这两个路人性质就好
①容斥求LCM

#include
#include
#include
#include
#include
#include
#include
#include using namespace std;
#define mmst(a, b) memset(a, b, sizeof(a))
#define mmcp(a, b) memcpy(a, b, sizeof(b))typedef long long LL;const LL mo&＃61;1e9&＃43;7;
const int N&＃61;1010000;int n;
LL ans&＃61;1,f[N],g[N];
bool b[N];LL cheng(LL a,LL b)
{LL res&＃61;1;for(;b;b>>&＃61;1,a&＃61;a*a%mo)if(b&1)res&＃61;res*a%mo;return res;
}int main()
{g[1]&＃61;f[1]&＃61;1;for(int i&＃61;2;i1]&＃43;f[i-2])%mo,g[i]&＃61;f[i];for(int i&＃61;2;i2);for(int j&＃61;i&＃43;i;jcin>>n;for(int i&＃61;1;i<&＃61;n;i&＃43;&＃43;){int x;scanf("%d",&x);b[x]&＃61;1;}for(int i&＃61;1;ibool ok&＃61;0;for(int j&＃61;i;jif(b[j]){ok&＃61;true;break;}if(ok)ans&＃61;ans*g[i]%mo;}cout<return 0;
}