LOJ#6102. 「2017 山东二轮集训 Day1」第三题 题解

题目链接

记斐波那契数列的第 (n) 项为 (F_n) .

结论1 : (gcd(F_n,F_m) = F_{gcd(n,m)})

这个应该是经典结论了。

大概就是,首先有 (F_{n+m} = F_{n-1}F_{m} + F_{n}F_{m+1}) 且 (gcd (F_n,F_{n-1}) = 1)

那么不难发现 (gcd(F_{n+m},F_m) = gcd(F_n,F_m)) .

结论2 : ( exttt{lcm}(S) = prodlimits_{T ∈ S,T eq ∅} gcd(T) ^ {(-1)^{|T|+1}})

不难发现这个式子和对每个质因数进行 (min-max) 容斥等价，于是得证。

考虑计算出每个 (F_{gcd(T)}) 的次数，那么直接 Dirichlet 前缀和 一下即可。

因为最后需要快速幂，所以复杂度为 (Theta (n log n)) . 如果不想写 Dirichlet 前缀和 , 也可以写 (Theta(n ln n)) 的暴力，但还是跑的飞快？

code :

#include <bits/stdc++.h>
#define LL unsigned long long
#define uint unsigned
using namespace std;
template <typename T> void read(T &x){
	static char ch; x = 0,ch = getchar();
	while (!isdigit(ch)) ch = getchar();
	while (isdigit(ch)) x = x * 10 + ch - '0',ch = getchar();
}
const uint P = 1e9 + 7; const int N = 1000005;
inline uint power(uint x,int y){
	if (y < 0) y += P-1;
	static uint r; r = 1; while (y){ if (y&1) r = (LL)r * x % P; x = (LL)x * x % P,y >>= 1; } return r;
}
int n,a[N]; uint fib[N];
int main(){
	register int i,j; uint ret = 1;
	read(n); while (n--) read(i),a[i] = 1;
	n = 1000000; while (n && !a[n]) --n;
	for (fib[1] = 1,i = 2; i <= n; ++i) fib[i] = (fib[i-1] + fib[i-2] >= P) ? (fib[i-1] + fib[i-2] - P) : (fib[i-1] + fib[i-2]);
	for (i = 1; i <= n; ++i) for (j = i<<1; j <= n; j += i) if (a[j]){ a[i] = 1; break; }
	for (i = n; i ; --i) for (j = i<<1; j <= n; j += i) a[i] -= a[j];
	for (i = 1; i <= n; ++i) if (a[i]) ret = (LL)ret * power(fib[i],a[i]) % P;
	cout << ret << '
';
	return 0;
}