@hdu - 6428@ Problem C. Calculate

以你之姓@ 2023-06-01 13:58 22阅读 0赞

*  @description@
 *  @solution@
 *  @accepted code@
 *  @details@

--------------------

## @description@ ##

给定 A, B, C，求：  
\\\[\\sum\_\{i=1\}^\{A\}\\sum\_\{j=1\}^\{B\}\\sum\_\{k=1\}^\{C\}\\phi(gcd(i, j^2, k^3))\\mod 2^\{30\}\\\]

**Input**  
第一行给定一个整数 T，描述数据组数。  
接下来每组数据包含三个整数 A, B, C，含义如上。  
1 ≤ T ≤ 10, 0 < A, B, C ≤ 10^7

**Output**  
对于每组数据，输出答案 mod 2^30。

**Sample Input**  
4  
96 93 95  
970 906 893  
92460 95043 54245  
9760979 8053227 7156842  
**Sample Output**  
1114536  
28070648  
388873924  
623507672

## @solution@ ##

套路反演一波：  
\\\[ans = \\sum\_\{d=1\}\\phi(d)\*(\\sum\_\{d|p\}\\mu(\\frac\{p\}\{d\})\*(\\sum\_\{i=1\}^\{A\}\[p|i\])\*(\\sum\_\{j=1\}^\{B\}\[p|j^2\])\*(\\sum\_\{k=1\}^\{C\}\[p|k^3\]))\\\]

注意到其实 \\((\\sum\_\{i=1\}^\{A\}\[p|i\]) = \\lfloor\\frac\{A\}\{p\}\\rfloor\\)，是比较好求解的，但是另外两项不能直接这么类比着做。  
考虑从唯一分解式的角度去理解。令 \\(p = \\prod\_\{i=0\}a\_i^\{b\_i\}, j = \\prod\_\{i=0\}a\_i^\{c\_i\}\\)。  
如果 \\(p|j^2\\)，则有 \\(b\_i \\le 2c\_i\\)，于是 \\(\\lceil\\frac\{b\_i\}\{2\}\\rceil \\le c\_i\\)。  
我们令 \\(f\[p\] = \\prod\_\{i=0\}a\_i^\{\\lceil\\frac\{b\_i\}\{2\}\\rceil\}\\)，则条件等价转为 \\(f\[p\]|j\\)。类比得到 \\(g\[p\]\\) 的定义以及 \\(g\[p\]|k\\)。

所以答案式变为：  
\\\[ans = \\sum\_\{d=1\}\\phi(d)\*(\\sum\_\{d|p\}\\mu(\\frac\{p\}\{d\})\*\\lfloor\\frac\{A\}\{p\}\\rfloor\*\\lfloor\\frac\{B\}\{f\[p\]\}\\rfloor\*\\lfloor\\frac\{C\}\{g\[p\]\}\\rfloor\\\]

那么怎么快速求 f\[p\] 或 g\[p\] 呢？可以发现 \\(f\[p\] = \\prod\_\{i=0\}f\[a\_i^\{b\_i\}\]\\)，也就是说它是积性函数。  
所以我们就使用线性筛任意积性函数的技巧即可。[这里有一个可以参考的连接][Link 1]。  
我实现上跟那个博客写得不大一样（不过思想是一致的嗯嗯）。

然后我们考虑 \\(\\sum\_\{d=1\}\\phi(d)\*\\mu(\\frac\{p\}\{d\})\\)，发现它是两个积性函数的狄利克雷卷积，而众所周知这也是个积性函数。  
然后就可以愉快地再次任意函数线性筛一波。

最后枚举 p 算答案。时间复杂度 O(n)。

## @accepted code@ ##

#include<cstdio> const int MOD = (1<<30) - 1; const int MAXN = int(1E7); inline int mul(int a, int b) {return (1LL*a*b)&MOD;} int prm[MAXN + 5], pcnt = 0; int low[MAXN + 5], f[MAXN + 5], g[MAXN + 5], h[MAXN + 5]; void sieve() { low[1] = f[1] = g[1] = h[1] = 1; for(int i=2;i<=MAXN;i++) { if( !low[i] ) { low[i] = i, prm[++pcnt] = i; f[i] = i - 2, g[i] = h[i] = i; long long p = 1LL*i*i; for(int j=2;p<=MAXN;p*=i,j++) { low[p] = p; f[p] = p/i/i*(i-1)*(i-1); g[p] = g[p/i]; if( (j-1) % 2 == 0 ) g[p] *= i; h[p] = h[p/i]; if( (j-1) % 3 == 0 ) h[p] *= i; } } for(int j=1;1LL*i*prm[j]<=MAXN;j++) { if( i % prm[j] == 0 ) { if( i != low[i] ) { low[i*prm[j]] = low[i]*prm[j]; f[i*prm[j]] = f[i/low[i]]*f[prm[j]*low[i]]; g[i*prm[j]] = g[i/low[i]]*g[prm[j]*low[i]]; h[i*prm[j]] = h[i/low[i]]*h[prm[j]*low[i]]; } break; } else { low[i*prm[j]] = prm[j]; f[i*prm[j]] = f[i]*f[prm[j]]; g[i*prm[j]] = g[i]*g[prm[j]]; h[i*prm[j]] = h[i]*h[prm[j]]; } } } } void solve() { int A, B, C, ans = 0; scanf("%d%d%d", &A, &B, &C); for(int i=1;i<=A;i++) ans = (1LL*ans + 1LL*mul(mul(f[i], A/i), mul(B/g[i], C/h[i])))&MOD; printf("%d\n", ans); } int main() { sieve(); int T; scanf("%d", &T); for(int i=1;i<=T;i++) solve(); }

## @details@ ##

因为是对 2^30 取模，所以可以用位运算加速（虽然我不知道能加到多快，不过应该挺快的）。

转载于:https://www.cnblogs.com/Tiw-Air-OAO/p/11304614.html

[Link 1]: https://www.cnblogs.com/zhoushuyu/p/8275530.html