[51Nod 1355]斐波那契的最小公倍数

danihao123 posted @ 2018年4月10日 11:27 in 题解 with tags 容斥原理 莫比乌斯反演 51nod 狄利克雷卷积 MIN-MAX容斥 , 8 阅读
转载请注明出处:http://danihao123.is-programmer.com/

MIN-MAX容斥第一题……

众所周知斐波那契数有个非常好的性质:

\[\gcd(\{f_i | i\in T\}) = f_{\gcd\{T\}}\]

但很不幸的事情是,lcm没有类似的性质。那我们就考虑怎么把lcm改成gcd。

根据MIN-MAX容斥,可以得到这个式子(可以理解为对指数的容斥。这里设\(S\)为全集):

\[\prod_{T\subseteq S, T\neq\emptyset} f_{\gcd\{T\}}^{(-1)^{|T| + 1}}\]

gcd套在上面非常烦人,考虑用狄利克雷卷积去化解它。考虑有个函数\(g\)满足\(f_n = \prod_{d|n} g(d)\),然后xjb化简一下之后柿子变成:

\[\prod_{d} g(d)^{\sum_{T\subseteq S, T\neq\emptyset, \forall x\in T, d | x}(-1)^{|T| + 1}}\]

再去考虑那个指数。当且仅当\(d\in S\)时,\(g(d)\)才会对答案做贡献。并且无论\(S\)中\(d\)的约数有多少个(只要大于),最后指数肯定都是1。因为其实大于零的情况那个指数也是一个所有最小值都是1的MIN-MAX容斥……这样求出来最大值肯定是1了,那个指数自然就是1。

于是乎柿子变成了:

\[\prod_{\exists x\in S, d | x} g(d)\]

然后搞出来\(S\)中所有数的约数很容易。当务之急就是求\(g\)了(这里其实就是莫比乌斯反演了)。不过球莫比乌斯函数反而让问题复杂化了……移下项可以发现:

\[g(n) = f_n\cdot (\prod_{d | n, d\neq n} g(d))^{-1}\]

然后就很愉快的搞出来了(逃

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <utility>
#include <queue>
const int maxn = 1000005;
using ll = long long;
const ll ha = 1000000007LL;
ll pow_mod(ll a, ll b) {
  ll ans = 1LL, res = a;
  while(b) {
    if(1LL & b) {
      ans = (ans * res) % ha;
    }
    res = (res * res) % ha;
    b /= 2LL;
  }
  return ans;
}
ll inv(ll x) {
  return pow_mod(x, ha - 2LL);
}

ll f[maxn], g[maxn];
void process_f() {
  int N = 1000000;
  f[0] = 0LL; f[1] = 1LL;
  for(int i = 2; i <= N; i ++) {
    f[i] = (f[i - 1] + f[i - 2]) % ha;
  }
  std::fill(g + 1, g + 1 + N, 1LL);
  for(int i = 1; i <= N; i ++) {
    g[i] = (f[i] * inv(g[i])) % ha;
    for(int j = i * 2; j <= N; j += i) {
      g[j] = (g[j] * g[i]) % ha;
    }
  }
#ifdef LOCAL
  puts("g has been processed!");
#endif
}

bool vis[maxn];
void process_vis() {
  int N = 1000000;
  for(int i = 1; i <= N; i ++) {
    for(int j = i * 2; j <= N; j += i) {
      vis[i] = (vis[i] || vis[j]);
    }
  }
}

int main() {
  process_f();
  int n; scanf("%d", &n);
  for(int i = 1; i <= n; i ++) {
    int a; scanf("%d", &a);
    vis[a] = true;
  }
  process_vis();
  ll ans = 1LL;
  for(int i = 1; i <= 1000000; i ++) {
    if(vis[i]) {
      ans = (ans * g[i]) % ha;
    }
  }
  printf("%lld\n", ans);
  return 0;
}
  • 无匹配
  • 无匹配

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter