【LG

admin管理员组

文章数量:1122850

【LG

P4449 于神之怒加强版

给定 n , m , k n,m,k n,m,k，计算

∑ i = 1 n ∑ j = 1 m gcd ⁡ ( i , j ) k \sum_{i=1}^n \sum_{j=1}^m \gcd(i,j)^k ∑i=1n​∑j=1m​gcd(i,j)k 对 1 0 9 + 7 10^9 + 7 109+7 取模的结果。

---

推柿子：

假设 n ≤ m n\le m n≤m

∑ i = 1 n ∑ j = 1 m gcd ⁡ ( i , j ) k \sum_{i=1}^n \sum_{j=1}^m \gcd(i,j)^k ∑i=1n​∑j=1m​gcd(i,j)k

= ∑ d = 1 n d k ∑ i = 1 ⌊ n d ⌋ ∑ j = 1 ⌊ m d ⌋ [ gcd ⁡ ( i , j ) = 1 ] =\sum_{d=1}^nd^k\sum_{i=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{d}\right\rfloor}[\gcd(i,j)=1] =∑d=1n​dk∑i=1⌊dn​⌋​∑j=1⌊dm​⌋​[gcd(i,j)=1]

= ∑ d = 1 n d k ∑ u = 1 ⌊ n d ⌋ μ ( u ) ∗ ⌊ n d u ⌋ ∗ ⌊ m d u ⌋ =\sum_{d=1}^nd^k\sum_{u=1}^{\left\lfloor\frac{n}{d}\right\rfloor}\mu(u)* \left\lfloor\frac{n}{du}\right\rfloor* \left\lfloor\frac{m}{du}\right\rfloor =∑d=1n​dk∑u=1⌊dn​⌋​μ(u)∗⌊dun​⌋∗⌊dum​⌋

设 T = d u T=du T=du，

= ∑ T = 1 n ⌊ n T ⌋ ∗ ⌊ m T ⌋ ∑ d ∣ T T d k ∗ μ ( T d ) =\boxed{\sum_{T=1}^n\left\lfloor\frac{n}{T}\right\rfloor* \left\lfloor\frac{m}{T}\right\rfloor\sum_{d|T}^Td^k*\ \mu(\frac{T}{d})} =T=1∑n​⌊Tn​⌋∗⌊Tm​⌋d∣T∑T​dk∗ μ(dT​)​

以上都是基本操作。

---

易知，框起来的柿子中，前半部分可以直接用整除分块做，所以重点就是求后半部分。

设 f ( x ) = ∑ d ∣ x x d k ∗ μ ( x d ) f(x)=\sum_{d|x}^xd^k*\ \mu(\frac{x}{d}) f(x)=∑d∣xx​dk∗ μ(dx​)。

显然，当 k = 1 k=1 k=1 时它就是个卷积。易得： f = I d k ∗ μ f=Id_k* \mu f=Idk​∗μ。

根据积性函数的性质可得：在 I d k Id_k Idk​ 和 μ \mu μ 都是积性函数的情况下， f f f 也必然是个积性函数。

所以： f ( x ) = ∏ f ( p i a i ) f(x)=\prod f(p_i^{a_i}) f(x)=∏f(piai​​)

即可以线性求 f ( x ) f(x) f(x)。

---

考虑求 f ( p i a i ) f(p_i^{a_i}) f(piai​​)。

f ( p i a i ) = ∑ d ∣ p i a i x d k ∗ μ ( p i a i d ) f(p_i^{a_i})=\sum_{d|p_i^{a_i}}^x d^k*\ \mu(\frac{p_i^{a_i}}{d}) f(piai​​)=∑d∣piai​​x​dk∗ μ(dpiai​​​)

根据莫比乌斯函数的性质，有：当且仅当 d = p i a i − 1 d=p_i^{a_i-1} d=piai​−1​ 或 d = p i a i d=p_i^{a_i} d=piai​​ 时 μ ( p i a i d ) \mu(\frac{p_i^{a_i}}{d}) μ(dpiai​​​) 的值不为 0。

所以：$f(p_i^{a_i})=p_{i}{k* a_i} - p_{i}^{k* (a_i-1)} = (p_i^k-1)* p_{i}^{k* (a_i-1)} $

• 当 a i > 1 a_i>1 ai​>1 时，也有：$f(p_i^{{a_i-1})=p_{i}}{k* (a_i-1)} - p_{i}^{k* (a_i-2)} = (p_i^k-1)* p_{i}^{k* (a_i-2)} $

  综上，得： f ( p i a i ) = f ( p i a i − 1 ) ∗ p i k ( a i > 1 ) \boxed{f(p_i^{a_i})=f(p_i^{a_i-1})* p_i^k\ \ (a_i>1)} f(piai​​)=f(piai​−1​)∗pik​  (ai​>1)​

• 当 a i = 1 a_i=1 ai​=1 时， f ( p i a i ) = p j k − 1 \boxed{f(p_i^{a_i})=p_j^k-1} f(piai​​)=pjk​−1​

---

推到这里之后就可以根据积性函数的性质线性筛了。

CODE：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;#define int long long
#define maxm 5000005
#define maxn 5000000
#define mod 1000000007int t, n, m, k;
int prm[maxm], tot, f[maxm], sum[maxm], low[maxn];
bool vis[maxm];inline int power(int x, int p)
{int res = 1;while(p > 0){if(p & 1) res = res * x % mod;p /= 2, x = x * x % mod;}return res;
}inline void pre()
{vis[1] = f[1] = sum[1] = 1;for(int i = 2; i <= maxn; ++i){if(!vis[i])f[i] = (-1 + power(i, k) + mod) % mod,prm[++tot] = i;for(int j = 1; j <= tot and i * prm[j] <= maxn; ++j){vis[i * prm[j]] = 1;if(i % prm[j] == 0){f[i * prm[j]] = f[i] * power(prm[j], k) % mod;break;}f[i * prm[j]] = f[i] * f[prm[j]] % mod;}sum[i] = sum[i - 1] + f[i];}
}inline int slv(int a, int b)
{int ans = 0;for(int l = 1, r; l <= a; l = r + 1){r = min(a / (a / l), b / (b / l));ans = (ans + (sum[r] - sum[l - 1] < 0 ? sum[r] - sum[l - 1] + mod : sum[r] - sum[l - 1]) * (a / l) % mod * (b / l) % mod) % mod;	}return ans;
}signed main()
{scanf("%lld %lld", &t, &k);pre();while(t--){scanf("%lld %lld", &n, &m);if(n > m) swap(n, m);printf("%lld\n", slv(n, m));}return 0;
}

---

—— E n d End End——

本文标签： LG