锐客网

  1. 首页 > it技术 > >

HDU|HDU 5528 狄利克雷卷积

数论HDU狄利克雷卷积

题目链接
题意：
给定 T ( ≤ 2 e 4 ) T (\leq 2e4) T(≤2e4)组数据，每组数据给出一个整数 n ( n ≤ 1 e 9 ) n(n \leq 1e9) n(n≤1e9)，求：
A n s = ∑ m ∣ n ∑ i = 0 m ? 1 ∑ i = 0 m ? 1 [ ( i ? j ) % m > 0 ] Ans = \sum_{m|n}\sum_{i=0}^{m-1}\sum_{i=0}^{m-1}[(i*j) \% m > 0] Ans=m∣n∑?i=0∑m?1?i=0∑m?1?[(i?j)%m>0]
思路：
正难则反
转化公式为：
A n s = ∑ m ∣ n ( m 2 ? ∑ i = 0 m ? 1 ∑ i = 0 m ? 1 [ ( i ? j ) % m = 0 ] ) Ans = \sum_{m|n} (m^2 - \sum_{i=0}^{m-1}\sum_{i=0}^{m-1}[(i*j) \% m = 0]) Ans=m∣n∑?(m2?i=0∑m?1?i=0∑m?1?[(i?j)%m=0])
令
F [ n ] = ∑ i = 0 m ? 1 ∑ i = 0 m ? 1 [ ( i ? j ) % m = 0 ] F[n] = \sum_{i=0}^{m-1}\sum_{i=0}^{m-1}[(i*j) \% m = 0] F[n]=i=0∑m?1?i=0∑m?1?[(i?j)%m=0]
则
A n s = ∑ m ∣ n m 2 ? F [ m ] Ans = \sum_{m|n} m^2 - F[m] Ans=m∣n∑?m2?F[m]
【HDU|HDU 5528 狄利克雷卷积】通过打表可以发现， F F F为积性函数
故：
G [ n ] = ∑ m ∣ n F [ m ] = ∑ m ∣ n F [ m ] ? I [ n / m ] G[n] = \sum_{m|n}F[m] = \sum_{m|n}F[m]*I[n/m] G[n]=m∣n∑?F[m]=m∣n∑?F[m]?I[n/m]
两个积性函数的狄利克雷卷积仍为积性函数
故：
当 n = ∏ i = 1 t p i k i 当 n = \prod_{i=1}^tp_i^{k_i} 当n=i=1∏t?piki??
有：
G [ n ] = ∏ i = 1 t G [ p i k i ] = ∏ i = 1 t ∑ j = 0 k i F ( p i j ) G[n] = \prod_{i=1}^tG[p_i^{k_i}] = \prod_{i=1}^t\sum_{j=0}^{k_i}F(p_i^j) G[n]=i=1∏t?G[piki??]=i=1∏t?j=0∑ki??F(pij?)
故G[n]通过分解质因数可以高效求解
前面的约数平方和因为也是积性函数，同理可求。
以上。
代码：

#include #include #include #include #include using namespace std; typedef unsigned long long ull; const int A = 1e5 + 10; int pri[A], tot; bool vis[A]; void Init(){ tot = 0; for (int i = 2; i < A; i++) { if (!vis[i]) pri[++tot] = i; for (int j = 1; j <= tot && i * pri[j] < A; j++) { vis[i * pri[j]] = 1; if (i % pri[j] == 0) break; } } }ull fast_pow(ull n, int m){ ull res = 1; while(m){ if (m&1) res *= n; n = n * n; m >>= 1; } return res; }ull Fun1(int p, int r){ return fast_pow(p, 2*r); }ull Fun2(ull p, ull r){ if (r == 0) return 1; ull now = fast_pow(p, r - 1); return (now*p*(r+1) - r*now); }ull calc(int n){ ull res1 = 1, res2 = 1; for (int i = 1; i <= tot && pri[i] * pri[i] <= n; i++) { if (n % pri[i] == 0) { int cnt = 0; while (n % pri[i] == 0) { n /= pri[i]; cnt++; } ull tem1 = 0, tem2 = 0; for (int j = 0; j <= cnt; j++) { tem1 += Fun1(pri[i], j); tem2 += Fun2(pri[i], j); } res1 *= tem1; res2 *= tem2; } } if (n > 1) { res1 *= Fun1(n, 0) + Fun1(n, 1); res2 *= Fun2(n, 0) + Fun2(n, 1); } return (res1 - res2); }int main(){ Init(); ios::sync_with_stdio(false); cin.tie(0); int T; cin >> T; while (T--) { int n; cin >> n; cout << calc(n) << endl; } return 0; }

    推荐阅读


    上一篇：后缀平衡树|hashit

    下一篇：Android应用统计-使用时长及次数统计（四）