my cnblogs

题目描述

给你 $n$ 个整数 $a_i$ 叫你求：

$$\sum_{i_1|a_1}\sum_{i_2|a_2}\sum_{i_3|a_3}\cdots\sum_{i_n|a_n}\varphi(i_1i_2i_3\cdots i_n) $$

简要思路

发现对于欧拉函数 $\varphi(n)$ 为积性函数，所以不难想到对于每一个质数 $p$ 考虑贡献。

我们假设现在考虑到的质数为 $p$ ，令对于每一个 $a_i$ 质数 $p$ 所对的最大指数为 $b_i$ 。 那么我们可以得到此时 $p$ 的贡献为：

$$\begin{split} S &= \sum_{i_1=0}^{b_1}\sum_{i_2=0}^{b_2}\sum_{i_3=0}^{b_3}\cdots\sum_{i_n=0}^{b_n} \varphi(p^{i_1}p^{i_2}p^{i_3}\cdots p^{i_n})\\ &=\sum_{i_1=0}^{b_1}\sum_{i_2=0}^{b_2}\sum_{i_3=0}^{b_3}\cdots\sum_{i_n=0}^{b_n} \varphi(p^{i_1+i_2+i_3+\cdots+i_n}) \end{split} $$

考虑到对于 $\varphi(p^n)$ 有这样的公式：

$$\varphi(p^n)=p^n\times\frac{p-1}{p}$$

所以上式可以表示为：

$$\begin{split} S&=\sum_{i_1=0}^{b_1}\sum_{i_2=0}^{b_2}\sum_{i_3=0}^{b_3}\cdots\sum_{i_n=0}^{b_n} (p^{i_1+i_2+i_3+\cdots+i_n}\times\frac{p-1}{p})\\ &=\frac{p-1}{p}\times\sum_{i_1=0}^{b_1}\sum_{i_2=0}^{b_2}\sum_{i_3=0}^{b_3}\cdots\sum_{i_n=0}^{b_n}p^{i_1+i_2+i_3+\cdots+i_n} \end{split} $$

看上去没有任何问题，但是发现当 $i_1=i_2=i_3=\cdots=i_n=0$ 时有一定的缺陷，所以改成：

$$\begin{split} S&=\sum_{i_1=0}^{b_1}\sum_{i_2=0}^{b_2}\sum_{i_3=0}^{b_3}\cdots\sum_{i_n=0}^{b_n} (p^{i_1+i_2+i_3+\cdots+i_n}\times\frac{p-1}{p})\\ &=\frac{p-1}{p}\times\sum_{i_1=0}^{b_1}\sum_{i_2=0}^{b_2}\sum_{i_3=0}^{b_3}\cdots\sum_{i_n=0}^{b_n}p^{i_1+i_2+i_3+\cdots+i_n}\\ &=\left[\sum_{i_1=0}^{b_1}\sum_{i_2=0}^{b_2}\sum_{i_3=0}^{b_3}\cdots\sum_{i_n=0}^{b_n}p^{i_1+i_2+i_3+\cdots+i_n}-1\right]\times\frac{p-1}{p}+1 \end{split} $$

现在发现后面的那一部分包括那个 $-1$ 都是死的，所要计算的也就是下面这个式子：

$$\sum_{i_1=0}^{b_1}\sum_{i_2=0}^{b_2}\sum_{i_3=0}^{b_3}\cdots\sum_{i_n=0}^{b_n} p^{i_1+i_2+i_3+\cdots+i_n} $$

我们尝试着把这个式子拆开来看一下：

$$\begin{split} S'&=\sum_{i_1=0}^{b_1}\sum_{i_2=0}^{b_2}\sum_{i_3=0}^{b_3}\cdots\sum_{i_n=0}^{b_n} p^{i_1+i_2+i_3+\cdots+i_n}\\ &=\sum_{i_1=0}^{b_1}p^{i_1}\sum_{i_2=0}^{b_2}\sum_{i_3=0}^{b_3}\cdots\sum_{i_n=0}^{b_n} p^{i_2+i_3+\cdots+i_n}\\ &=\sum_{i_1=0}^{b_1}p^{i_1}\sum_{i_2=0}^{b_2}p^{i_2}\sum_{i_3=0}^{b_3}p^{i_3} \cdots\sum_{i_n=0}^{b_n}p^{i_n}\\ &=\prod_{i=1}^n(1+p+p^2+\cdots +p^{b_i}) \end{split} $$

然后对所有的质数 $p$ 去一个乘积就可以了，代码很简单。

点击查看代码

#pragma GCC optimize(2)

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>

#define File(a) freopen(a".in", "r", stdin), freopen(a".out", "w", stdout)

const int mod = 1e9 + 7;
const int M = 1e7 + 5;
const int N = 1e5 + 5;

int n, a[N], tag[M];

inline int power(int a, int n) {
  int ret = 1;
  while (n) {
    if (n & 1) ret = 1ll * ret * a % mod;
    a = 1ll * a * a % mod;
    n /= 2;
  }
  return ret;
}

signed main(void) {
  std::cin >> n;
  for (int i = 1; i <= M - 5; i++) tag[i] = 1;
  for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
  int ans = 1;
  for (int i = 1; i <= n; i++) {
    int t = a[i], num = 0, mul = 1, ss = 0;
    for (int j = 2; j * j <= t; j++) {
      if (t % j) continue;
      num = 0; mul = 1; ss = 0;
      while (t % j == 0) t /= j, num ++;
      for (int k = 0; k <= num; k ++) {
        ss = (0ll + ss + mul) % mod;
        mul = 1ll * mul * j % mod;
      }
      tag[j] = 1ll * tag[j] * ss % mod;
    }
    if (t > 1) {
      ss = 1 + t;
      tag[t] = (1ll * tag[t] * ss) % mod;
    }
  }
  for (int i = 2; i <= M - 5; i++) {
    if (tag[i] == 1) continue;
    int mul = 1ll * (tag[i] - 1) * (i - 1) % mod * power(i, mod - 2) % mod + 1;
    mul = (1ll * mul % mod + mod) % mod;
    ans = 1ll * ans * mul % mod;
  }
  std::cout << ans << std::endl;
  return 0;
}