51nod

# Solution

Orz 知乎大佬：张一钊的回答

$$lcm(f_S)=\prod_{T\subseteq S}\gcd(f_T)^{(-1)^{|T|-1}}=\prod_{T\subseteq S}f_{\gcd(f_T)}^{(-1)^{|T|-1}}$$

$$lcm(f_S)=\prod_{T\subseteq S}\biggl(\prod_{d|\gcd(f_T)}g_d \biggr)^{(-1)^{|T|-1}}$$

$$=\prod_{T\subseteq S} \prod_{d}g_d^{\sum_{T\subseteq S,d|\gcd(f_T)}{(-1)^{|T|-1}}}$$

$$\sum_{T\subseteq S,d|\gcd(f_T)}{(-1)^{|T|-1}}=[\exists_{x\in S} d|x]$$

$$\sum_{i=1}^l (-1)^{i-1}\binom l i=1$$

$$=\prod_{\exists d|x \in S}g(d)$$

$$g(n)=f(n)*\biggl(\prod_{d|n,d\not=n} g(d) \biggr)^{-1}$$

# Code

#include <cstdio>
#define rg register
using namespace std;
typedef long long ll;
const int maxn=50010,maxm=1000010,mod=1e9+7;
template <typename Tp> inline int getmin(Tp &x,Tp y){return y<x?x=y,1:0;}
template <typename Tp> inline int getmax(Tp &x,Tp y){return y>x?x=y,1:0;}
template <typename Tp> inline void read(Tp &x)
{
x=0;int f=0;char ch=getchar();
while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
if(ch=='-') f=1,ch=getchar();
while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
if(f) x=-x;
}
int n,m,tmp,ans=1,f[maxm],g[maxm],vis[maxm];
inline int pls(int x,int y){return x+y>=mod?x+y-mod:x+y;}
int power(int x,int y)
{
int res=1;
for(;y;y>>=1,x=(ll)x*x%mod)
if(y&1)
res=(ll)res*x%mod;
return res;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
f[1]=g[1]=1;
for(rg int i=2;i<=m;i++) f[i]=g[i]=pls(f[i-1],f[i-2]);
for(rg int i=1;i<=m;i++)
{
tmp=power(g[i],mod-2);
for(rg int j=i<<1;j<=m;j+=i)
g[j]=(ll)g[j]*tmp%mod;
}
for(rg int i=1;i<=m;i++)
for(rg int j=i;j<=m;j+=i)
if(vis[j])
{ans=(ll)ans*g[i]%mod;break;}
printf("%d\n",ans);
return 0;
}