LOJ6102「2017 山东二轮集训 Day1」第三题 【min-max容斥，反演】
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |
题目描述：输入一个大小为\(n\)的集合\(S\)，求\(\text{lcm}_{k\in S}f_k\)，其中\(f_k\)是第$$个Fibonacci数。
数据范围：\(n\le 5\times 10^4,u\le 10^6\)
数论经典题？
首先你要想到min-max容斥。
\]
然后你知道\(\gcd(f_a,f_b)=f_\gcd(a,b)\)，所以。
\]
不知道为什么你开始反演，设\(f_n=\prod\limits_{d|n}g_d\)，则\(g_n=\prod\limits_{d|n}f_{d}^{\mu(\frac{n}{d})}\)。
\text{lcm}(f_S)&=\prod_{\varnothing\ne T\subseteq S}(\prod_{d|\gcd(T)}g_d)^{(-1)^{|T|-1}} \\
&=\prod_{d}g_d^{\sum\limits_{\varnothing\ne T\subseteq S,d|T}(-1)^{|T|-1}}
\end{aligned}
\]
我们看看指数是啥。设\(S_d=\{n|n\in S\and d|n\}\)。
\]
所以
\]
直接做，时间复杂度\(O(k\log k)\)
code
```cpp
#include
#define Rint register int
using namespace std;
typedef long long LL;
const int mod = 1e9 + 7, N = 1000003;
int n, a[N], mx, f[N], g[N], ans = 1;
bool vis[N];
inline int add(int a, int b){return (a + b >= mod) ? (a + b - mod) : (a + b);}
inline int kasumi(int a, int b){
int res = 1;
while(b){
if(b & 1) res = (LL) res * a % mod;
a = (LL) a * a % mod; b >>= 1;
}
return res;
}
int main(){
scanf("%d", &n);
for(Rint i = 1;i
| 阿里云国内75折 回扣 微信号：monov8 |
| 阿里云国际，腾讯云国际，低至75折。AWS 93折 免费开户实名账号 代冲值 优惠多多 微信号：monov8 飞机：@monov6 |