首页 > 其他分享 >【题解】DZY Loves Math V

【题解】DZY Loves Math V

时间:2022-09-25 00:45:39浏览次数:51  
标签:int 题解 sum varphi times cdots split DZY Math

题目描述

给你 \(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;
}

标签:int,题解,sum,varphi,times,cdots,split,DZY,Math
From: https://www.cnblogs.com/Oier-GGG/p/16727066.html

相关文章

  • Linux 逻辑卷&精简卷报错问题解决
    一、 故障描述现象1:oraclelog目录提示坏道信息,进行修复后执行删除文件操作,目录不可使用。现象2:lsblk看到目录出现重复,并且有tmeta,tdata卷出现(图一)现象3:message日志出......
  • 尚品汇后台管理项目:刷新页面后空白问题解决方案
    问题描述:跟着老师敲得项目代码,在配置动态路由后出现了除home首页外其他页面只要点击浏览器的刷新按钮就会空白的问题home首页刷新可以正常显示   其他页面刷新后......
  • luogu P7632 题解
    一.思路我们可以先把时间换成以秒为单位的,然后在枚举每一秒时谁领先。二.重要点我们可以用string读入时间,再用一个函数以秒为单位提取出来(在程序中的函数名:tiqu)......
  • NOIP2018 day1 题解
    心血来潮看了看18年的联赛,感觉自己进步很大==T1对于一个“波”来说,显然需要的次数为最大的数(波峰),对于多个“波”,就每次记录一下从波底到波峰的高度差即可,这可以用差分简......
  • SOJ1626 方珍 题解
    传送门题意给定一个\(n×n\)的方阵,其中第\(i\)行为\(A_{i,1},A_{i,2},...,A_{i,n}\)。对于\(A_i\)的所有区间,设\(f_i\)为其中第\(k_i\)大的\(mex\)值。给......
  • JOIG 2021/2022 F 题解
    链接题意:给定一张\(n\)个点,\(m\)条边的无向图(保证没有重边、自环)。边有两种,\(type=1\)时,经过后手中的数\(-1\);\(type=2\)时,经过后手中的数\(\div2\)下取整。给定......
  • CF1701E Text Editor 题解报告
    题意翻译给定两个字符串\(S,T\),初始时光标在串\(T\)尾部,你可以进行以下操作:\(\texttt{left}\):将光标向左移动一个字符,如光标在字符串最左侧则不移动。\(\texttt{ri......
  • CF Round 822 Div2 题解
    比赛链接A题SelectThreeSticks(签到)给定\(n\)根木棒,第\(i\)根木棒的长度为\(a_i\)。现在我们可以进行操作,每次操作选定一根木棒,将其长度增高或减少1。问至少需......
  • CF 教育场 135 题解
    比赛链接A题ColoredBalls:Revisited(签到)给定\(n\)种颜色的球,其中颜色\(i\)的球的数量是\(cnt_i\),保证\(\sum\limits_{i=1}^ncnt_i\)是奇数。在一次操作中,我......
  • Codeforces Round #822 Div.2 整场题解
    目前还有E,F没有更新。A.SelectThreeSticks直接对\(a\)排序,选出来的木棍一定是相邻三项,都往中间靠更优。B.Bright,Nice,Brilliant最优方案就是每一行第一个......