莫比乌斯反演小记
2020-04-29 16:01:00来源:博客园 阅读 ()
莫比乌斯反演小记
瞎搞写在前面
这是蒟蒻第一次写这么长的博文
\(gyh\ nb\),\(\text{OI-Wiki}\ nb\)
如果觉得写得凑合就点个支持吧\(qwq\)
前置知识
积性函数、狄利克雷卷积、数论分块(这一篇去找gyh吧我讲也讲不好)(有空慢慢补)
Mobius函数
定义
莫比乌斯函数\(\mu(n)\)定义为:
\[\mu(n)=\left\{ \begin{aligned} 1, & n=1 \\ (-1)^{s}, & n=p_1p_2…p_s(s为n的本质不同的质因子个数)\\0,&n有平方因子\end{aligned} \right.\]
其中\(p_1p_2…,p_s\)是不同素数。
可以看出,当\(n\)没有平方因子时,\(\mu(n)\)非零。
\(\mu\)也是积性函数。
性质
莫比乌斯函数具有如下的性质:
\[\sum_{d|n}\mu(d)=\epsilon(n)=[n=1] \]
使用狄利克雷卷积来表示,即
\[\mu*1=\epsilon \]
证明:
\(n=1\)时显然成立。
若\(n>1\),设\(n\)有\(s\)个不同的素因子,由于\(\mu(d)\neq0\)当且仅当\(d\)无平方因子,故\(d\)中每个素因子的指数只能为\(0\)或\(1\)。
若\(n\)的某个因子\(d\),有\(\mu(d)=(-1)^i\),则它由\(i\)个本质不同的质因子构成。因为质因子的总数为\(s\),所以满足上式的因子数有\(C_s^i\)个。
所以我们就可以对于原式,转化为枚举\(\mu(d)\)的值,同时运用二项式定理,故有
\[\sum_{d|n}\mu(d)=\sum_{i=0}^{s}C_s^i\times(-1)^i=\sum_{i=0}^{s}C_s^i\times(-1)^i\times 1^{s-i}=(1+(-1))^s \]
该式在\(s=0\)即\(n=1\)时为1,否则为\(0\)。
求莫比乌斯函数
因为莫比乌斯函数是积性函数,所以可以用线性筛
int n, cnt, p[A], mu[A];
bool vis[A];
void getmu() {
mu[1] = 1;
for (int i = 2; i <= n; i++) {
if (!vis[i]) mu[i] = -1, p[++cnt] = i;
for (int j = 1; j <= cnt && i * p[j] <= n; j++) {
vis[i * p[j]] = 1;
if (i % p[j] == 0) { mu[i * p[j]] = 0; break; }
mu[i * p[j]] -= mu[i];
}
}
}
莫比乌斯反演公式
设\(f(n)\),\(g(n)\)为两个数论函数。
如果有
\[f(n)=\sum\limits_{d|n}g(d) \]
则有
\[g(n)=\sum\limits_{d|n}\mu(d)f(\frac{n}{d}) \]
证明
-
法一:对原式做数论变换
-
\(\sum\limits_{d|n}g(d)\)替换\(f(n)\),即
\[\sum\limits_{d|n}\mu(d)f(\frac{n}{d})=\sum\limits_{d|n}\mu(d)\sum\limits_{k|\frac nd}g(k) \]
-
变换求和顺序得
\[\sum\limits_{k|n}g(k)\sum\limits_{d|\frac n k}\mu(\frac nk) \]
-
因为\(\sum\limits_{d|n}\mu(d)=[n=1]\),所以只有在\(\frac{n}{k}=1\)即\(n=k\)时才会成立,所以上式等价于
\[\sum\limits_{d|n}[n=k]g(k)=g(n) \]
得证
-
-
法二:利用卷积
原问题为:已知\(f=g*1\),证明\(g=f*\mu\)
转化:\(f*\mu=g*1*\mu=g*\varepsilon=g\)(\(1*\mu=\varepsilon\))
再次得证= =
小性质
\([\gcd(i,j)=1]\Leftrightarrow\sum\limits_{d|\gcd(i,j)}\mu(d)\)
证明
-
法一:
设\(n=\gcd(i,j)\),那么等式右边\(=\sum\limits_{d|n}\mu(d)=[n=1]=[\gcd(i,j)=1]=\)等式左边
-
法二:
利用单位函数暴力拆开:\([\gcd(i,j)=1]=\varepsilon(\gcd(i,j))=\sum\limits_{d|\gcd(i,j)}\mu(d)\)
做题思路&&应用
利用狄利克雷卷积可以解决一系列求和问题。常见做法是使用一个狄利克雷卷积替换求和式中的一部分,然后调换求和顺序,最终降低时间复杂度。
经常利用的卷积有\(\mu*1=\epsilon\)和\(\text{Id}=\varphi*1\)。
题
还是以题为主吧,但是做的题也会单独写题解,毕竟要多水几篇博客的嘛/huaji
洛谷 P2522 [HAOI2011]Problem b
题目链接
我的题解
有\(n\)组询问,每次给出\(a,b,c,d,k\),求\(\sum\limits_{x=a}^{b}\sum\limits_{y=c}^{d}[\gcd(x,y)=k]\)
设\(f(n,m)=\sum\limits_{i=1}^{n}\sum\limits_{j= 1}^{m}[\gcd(i,j)=k]\)
那么根据容斥原理,题目中的式子就转化成了\(f(b,d)-f(b, c - 1) - f(a - 1,d) + f(a - 1, c - 1)\)
所以我们接下来的问题就转化为了如何求\(f\)的值
现在来化简\(f\)的值
-
容易得出原式等价于$$\sum\limits_{i = 1}^{\lfloor\frac{n}{k}\rfloor}\sum\limits_{j = 1}^{\lfloor\frac{m}{k}\rfloor}[\gcd(i,j) = 1]$$
-
因为\(\epsilon(n) =\sum\limits_{d|n}\mu(d)=[n=1]\),由此可将原式化为
\[\sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{k}\rfloor}\sum\limits_{d|gcd(i,j)}\mu(d) \]
-
改变枚举对象并改变枚举顺序,先枚举\(d\),得
\[\sum\limits_{d=1}^{\min(n,m)}\mu(d)\sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}[d|i]\sum\limits_{j=1}^{\lfloor\frac{m}{k}\rfloor}[d|j] \]
也就是说当\(d|i\)且\(d|j\)时,\(d|\gcd(i,j)\)
-
易得\(1\sim \lfloor\frac{n}{k}\rfloor\)中一共有\(\lfloor\frac{n}{dk}\rfloor\)个\(d\)的倍数,同理\(1\sim \lfloor\frac{m}{k}\rfloor\)中一共有\(\lfloor\frac{m}{dk}\rfloor\)个\(d\)的倍数,于是原式化为$$\sum\limits_{d=1}^{\min(n,m)}\mu(d)\lfloor\frac{n}{dk}\rfloor\lfloor\frac{m}{dk}\rfloor$$
此时已经可以\(O(n)\)求解,但是过不了,因为有很多值相同的区间,所以可以用数论分块来做
先预处理\(\mu\),再用数论分块,复杂度\(O(n+T\sqrt n)\)
我的代码每次得分玄学,看评测机心情,建议自己写
/*
Author:loceaner
*/
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int A = 1e6 + 11;
const int B = 1e6 + 11;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
inline int read() {
char c = getchar(); int x = 0, f = 1;
for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return x * f;
}
int n, a, b, c, d, k, cnt, p[A], mu[A], sum[A];
bool vis[A];
void getmu() {
int MAX = 50010;
mu[1] = 1;
for (int i = 2; i <= MAX; i++) {
if (!vis[i]) mu[i] = -1, p[++cnt] = i;
for (int j = 1; j <= cnt && i * p[j] <= MAX; j++) {
vis[i * p[j]] = true;
if (i % p[j] == 0) break;
mu[i * p[j]] -= mu[i];
}
}
for (int i = 1; i <= MAX; i++) sum[i] = sum[i - 1] + mu[i];
}
int work(int x, int y) {
int ans = 0ll;
int max = min(x, y);
for (int l = 1, r; l <= max; l = r + 1) {
r = min(x / (x / l), y / (y / l));
ans += (1ll * x / (l * k)) * (1ll * y / (l * k)) * 1ll * (sum[r] - sum[l - 1]);
}
return ans;
}
void solve() {
a = read(), b = read(), c = read(), d = read(), k = read();
cout << work(b, d) - work(a - 1, d) - work(b, c - 1) + work(a - 1, c - 1) << '\n';
}
signed main() {
getmu();
int T = read();
while (T--) solve();
return 0;
}
洛谷 P3455 [POI2007]ZAP-Queries
题目链接
我的题解
有\(T\)组询问,每次询问求
\[\sum\limits_{x=1}^{a}\sum\limits_{y=1}^{b}[\gcd(x,y)=d] \]
因为我不喜欢用\(x、y、a、b、d\),所以一一对应换成\(i、j、n、m、k\)
直接淦式子
\[\begin{align*}&\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[\gcd(i,j)=k]\\=& \sum\limits_{i=1}^{\lfloor \frac nk\rfloor}\sum\limits_{j=1}^{\lfloor\frac mk\rfloor}[\gcd(i,j)=1]\\=&\sum\limits_{i=1}^{\lfloor \frac nk\rfloor}\sum\limits_{j=1}^{\lfloor\frac mk\rfloor}\sum\limits_{d|\gcd(i,j)}\mu(d)\\=&\sum\limits_{i=1}^{\lfloor \frac nk\rfloor}\sum\limits_{j=1}^{\lfloor\frac mk\rfloor}\sum\limits_{d|i}\sum _{d|j}\mu(d)\\=&\sum\limits_{d=1}^{\min(\lfloor\frac nk\rfloor,\lfloor\frac mk\rfloor)}\mu(d)\sum\limits_{i=1}^{\lfloor \frac nk\rfloor}\sum\limits_{j=1}^{\lfloor\frac mk\rfloor}\sum\limits_{d|i}\sum\limits_{d|j}1\\=&\sum\limits_{d=1}^{\min(\lfloor\frac nk\rfloor,\lfloor\frac mk\rfloor)}\mu(d)\sum\limits_{i=1}^{\lfloor \frac nk\rfloor}\sum\limits_{d|i}1\sum\limits_{j=1}^{\lfloor\frac mk\rfloor}\sum\limits_{d|j}1\\=&\sum\limits_{d=1}^{\min(\lfloor\frac nk\rfloor,\lfloor\frac mk\rfloor)}\mu(d)\lfloor\frac{\lfloor \frac nk\rfloor}d\rfloor\lfloor\lfloor\frac{\frac mk\rfloor}d\rfloor\\=&\sum\limits_{d=1}^{\min(\lfloor\frac nk\rfloor,\lfloor\frac mk\rfloor)}\mu(d)\lfloor\frac n{kd}\rfloor\lfloor\frac m{kd}\rfloor\end{align*} \]
现在就可以每次询问\(O(n)\)做这道题了
但是跑不过啊,不过显然可以数论分块,所以我们就可以\(O(\sqrt n)\)回答每次询问了
/*
Author:loceaner
*/
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int A = 5e5 + 11;
const int B = 1e6 + 11;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
inline int read() {
char c = getchar(); int x = 0, f = 1;
for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return x * f;
}
int n, m, k, mu[A], p[A], sum[A], cnt;
bool vis[A];
void getmu(int n) {
mu[1] = 1;
for (int i = 2; i <= n; i++) {
if (!vis[i]) p[++cnt] = i, mu[i] = -1;
for (int j = 1; j <= cnt && i * p[j] <= n; j++) {
vis[i * p[j]] = 1;
if (i % p[j] == 0) break;
mu[i * p[j]] -= mu[i];
}
}
for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + mu[i];
}
int solve(int n, int m, int k) {
int ans = 0, maxn = min(n, m);
for (int l = 1, r; l <= maxn; l = r + 1) {
r = min(n / (n / l), m / (m / l));
ans += (sum[r] - sum[l - 1]) * (n / (k * l)) * (m / (k * l));
}
return ans;
}
int main() {
getmu(50000);
int T = read();
while (T--) {
n = read(), m = read(), k = read();
cout << solve(n, m, k) << '\n';
}
return 0;
}
洛谷 P1829 [国家集训队]Crash的数字表格 / JZPTAB
题目链接
我的题解
求
\[\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\text{lcm}(i,j)(\bmod 20101009) \]
容易想到原式等价于
\[\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\frac{i* j}{\gcd(i,j)} \]
枚举\(i,j\)的最大公约数\(d\),显然\(\gcd(\frac id,\frac jd)=1\),即\(\frac id\)和\(\frac jd\)互质
\[\sum\limits_{i=1}^{n}\sum\limits_{j=1}^m\sum\limits_{d|i,d|j,\gcd(\frac id,\frac jd)=1}\frac{i*j}d \]
变换求和顺序
\[\sum\limits_{d=1}^{n}d\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}[\gcd(i,j)=1]i*j \]
记\(sum(n,m)=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}[\gcd(i,j)=1]i*j\)
对其进行化简,用\(\varepsilon(\gcd(i,j))\)替换\([\gcd(i,j)=1]\)
\[\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\sum\limits_{d|\gcd(i,j)}\mu(d)*i*j \]
转化为首先枚举约数
\[\sum\limits_{d=1}^{\min(n,m)}\sum\limits_{d|i}^{n}\sum\limits_{d|j}^{m}\mu(d)*i*j \]
设\(i=i'*d,j=j'*d\),则可以进一步转化
\[\sum\limits_{d=1}^{\min(n,m)}\mu(d)*d^2*\sum\limits_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{m}{d}\rfloor}i*j \]
前半段可以处理前缀和,后半段可以\(O(1)\)求,设
\[Q(n,m)=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}i*j=\frac{n*(n+1)}{2}*\frac{m*(m+1)}{2} \]
显然可以\(O(1)\)求解
到现在
\[sum(n,m)=\sum\limits_{d=1}^{\min(n,m)}\mu(d)*d^2*Q(\lfloor\frac nd \rfloor,\lfloor\frac md\rfloor) \]
可以用数论分块求解
回带到原式中
\[\sum\limits_{d=1}^{\min(n, m)}d*sum(\lfloor\frac nd \rfloor,\lfloor\frac md\rfloor) \]
又可以数论分块求解了
然后就做完啦
/*
Author:loceaner
*/
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
const int A = 1e7 + 11;
const int B = 1e6 + 11;
const int mod = 20101009;
const int inf = 0x3f3f3f3f;
inline int read() {
char c = getchar(); int x = 0, f = 1;
for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return x * f;
}
bool vis[A];
int n, m, mu[A], p[B], sum[A], cnt;
void getmu() {
mu[1] = 1;
int k = min(n, m);
for (int i = 2; i <= k; i++) {
if (!vis[i]) p[++cnt] = i, mu[i] = -1;
for (int j = 1; j <= cnt && i * p[j] <= k; ++j) {
vis[i * p[j]] = 1;
if (i % p[j] == 0) break;
mu[i * p[j]] = -mu[i];
}
}
for (int i = 1; i <= k; i++) sum[i] = (sum[i - 1] + i * i % mod * mu[i]) % mod;
}
int Sum(int x, int y) {
return (x * (x + 1) / 2 % mod) * (y * (y + 1) / 2 % mod) % mod;
}
int solve2(int x, int y) {
int res = 0;
for (int i = 1, j; i <= min(x, y); i = j + 1) {
j = min(x / (x / i), y / (y / i));
res = (res + 1LL * (sum[j] - sum[i - 1] + mod) * Sum(x / i, y / i) % mod) % mod;
}
return res;
}
int solve(int x, int y) {
int res = 0;
for (int i = 1, j; i <= min(x, y); i = j + 1) {
j = min(x / (x / i), y / (y / i));
res = (res + 1LL * (j - i + 1) * (i + j) / 2 % mod * solve2(x / i, y / i) % mod) % mod;
}
return res;
}
signed main() {
n = read(), m = read();
getmu();
cout << solve(n, m) << '\n';
}
洛谷 P2257 YY的GCD
题目链接
给定\(n,m\),求二元组\((x,y)\)的个数,满足\(1\leq x\leq n,1\leq y\leq m\),且\(gcd(x,y)\)是素数。
\(n,m\leq 10^7\),自带多组数据,至多\(10^{4}\)组数据。
思路与第一题Problem B类似,在这里不再赘述,只给出代码= =
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int A = 1e7 + 11;
inline int read() {
char c = getchar(); int x = 0, f = 1;
for ( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return x * f;
}
bool vis[A];
long long sum[A];
int prim[A], mu[A], g[A], cnt, n, m;
void get_mu(int n) {
mu[1] = 1;
for (int i = 2; i <= n; i++) {
if (!vis[i]) {
mu[i] = -1;
prim[++cnt] = i;
}
for (int j = 1; j <= cnt && prim[j] * i <= n; j++) {
vis[i * prim[j]] = 1;
if (i % prim[j] == 0) break;
else mu[prim[j] * i] = - mu[i];
}
}
for (int j = 1; j <= cnt; j++)
for (int i = 1; i * prim[j] <= n; i++) g[i * prim[j]] += mu[i];
for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + (long long)g[i];
}
signed main() {
int t = read();
get_mu(10000000);
while (t--) {
n = read(), m = read();
if (n > m) swap(n, m);
long long ans = 0;
for (int l = 1, r; l <= n; l = r + 1) {
r = min(n / (n / l), m / (m / l));
ans += 1ll * (n / l) * (m / l) * (sum[r] - sum[l - 1]);
}
cout << ans << '\n';
}
return 0;
}
洛谷 P3327 [SDOI2015]约数个数和
题目链接
求
\[\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}d(ij) \]
\(d(x)\)为\(x\)的约数个数和
需要用到
\[d(ij)=\sum\limits_{x|i}\sum\limits_{y|j}[\gcd(x,y)=1] \]
证明我也不会
然后自己推导吧,在此不再赘述
/*
Author:loceaner
*/
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int A = 5e5 + 11;
const int B = 1e6 + 11;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
inline int read() {
char c = getchar(); int x = 0, f = 1;
for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return x * f;
}
bool vis[A];
int n, m, p[A], mu[A], cnt, sum[A];
long long g[A], ans;
void getmu(int n) {
mu[1] = 1;
for (int i = 2; i <= n; i++) {
if (!vis[i]) mu[i] = -1, p[++cnt] = i;
for (int j = 1; j <= cnt && i * p[j] <= n; j++) {
vis[i * p[j]] = 1;
if (i % p[j] == 0) break;
mu[i * p[j]] -= mu[i];
}
}
for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + mu[i];
for (int i = 1; i <= n; i++) {
int ans = 0;
for (int l = 1, r; l <= i; l = r + 1) {
r = (i / (i / l));
ans += 1ll * (r - l + 1) * (i / l);
}
g[i] = ans;
}
}
signed main() {
int T = read();
getmu(50000);
while (T--) {
n = read(), m = read();
int maxn = min(n, m);
ans = 0;
for (int l = 1, r; l <= maxn; l = r + 1) {
r = min(n / (n / l), m / (m / l));
ans += 1ll * (sum[r] - sum[l - 1]) * 1ll * g[n / l] * 1ll * g[m / l];
}
cout << ans << '\n';
}
return 0;
}
洛谷 P4449 于神之怒加强版
求
\[\sum_{i=1}^{n}\sum_{j=1}^{m}\gcd(i,j)^k(\bmod 1e9+7) \]
还是直接淦式子
\[\begin{align*}&\sum_{i=1}^{n}\sum_{j=1}^{m}\gcd(i,j)^k\\=&\sum_{i=1}^{n}\sum_{j=1}^{m}\sum_{d=1}^{\min(n,m)}d^k[\gcd(i,j)=d]\\=&\sum_{d=1}^{\min(n,m)}d^k\sum_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac md\rfloor}[\gcd(i,j)=1]\\=&\sum_{d=1}^{\min(n,m)}d^k\sum_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac md\rfloor}\sum_{x|\gcd(i,j)}\mu(x)\\=&\sum_{d=1}^{\min(n,m)}d^k\sum_{i=1}^{\lfloor\frac nd\rfloor}\sum_{j=1}^{\lfloor\frac md\rfloor}\sum_{x|i,x|j}\mu(x)\\=&\sum_{d=1}^{\min(n,m)}d^k\sum_{x=1}^{\min(\lfloor\frac nd\rfloor,\lfloor\frac md\rfloor)}\mu(x)\sum_{i=1}^{\lfloor\frac nd\rfloor}[x|i]\sum_{j=1}^{\lfloor\frac md\rfloor}[x|j]\\=&\sum_{d=1}^{\min(n,m)}d^k\sum_{x=1}^{\min(\lfloor\frac nd\rfloor,\lfloor\frac md\rfloor)}\mu(x)\lfloor\frac n{dx}\rfloor\lfloor\frac m{dx}\rfloor\end{align*} \]
令\(P=dx\),则原式等于
\[\sum_{P=1}^{\min(n,m)}\lfloor\frac n{P}\rfloor\lfloor\frac m{P}\rfloor\sum_{d|P}d^k\mu(\frac Pd) \]
显然前面的\(\lfloor\frac n{P}\rfloor\lfloor\frac m{P}\rfloor\)部分可以分块求解。
现在考虑后面的一部分,令
\[g(n)=\sum_{d|n}d^k\mu(\frac nd) \]
容易得出这个函数是积性函数,所以我们就可以线性筛然后求出其前缀和
然后就做完了
/*
Author:loceaner
莫比乌斯反演
*/
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define int long long
using namespace std;
const int A = 5e6 + 11;
const int B = 1e6 + 11;
const int mod = 1e9 + 7;
const int inf = 0x3f3f3f3f;
inline int read() {
char c = getchar();
int x = 0, f = 1;
for( ; !isdigit(c); c = getchar()) if(c == '-') f = -1;
for( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);
return x * f;
}
bool vis[A];
int T, n, m, k, f[A], g[A], p[A], cnt, sum[A];
inline int power(int a, int b) {
int res = 1;
while (b) {
if (b & 1) res = res * a % mod;
a = a * a % mod, b >>= 1;
}
return res;
}
inline int mo(int x) {
if(x > mod) x -= mod;
return x;
}
inline void work() {
g[1] = 1;
int maxn = 5e6 + 1;
for (int i = 2; i <= maxn; i++) {
if (!vis[i]) { p[++cnt] = i, f[cnt] = power(i, k), g[i] = mo(f[cnt] - 1 + mod); }
for (int j = 1; j <= cnt && i * p[j] <= maxn; j++) {
vis[i * p[j]] = 1;
if (i % p[j] == 0) { g[i * p[j]] = g[i] * 1ll * f[j] % mod; break; }
g[i * p[j]] = g[i] * 1ll * g[p[j]] % mod;
}
}
for (int i = 2; i <= maxn; i++) g[i] = (g[i - 1] + g[i]) % mod;
}
inline int abss(int x) {
while (x < 0) x += mod;
return x;
}
signed main() {
T = read(), k = read();
work();
while (T--) {
n = read(), m = read();
int maxn = min(n, m), ans = 0;
for (int l = 1, r; l <= maxn; l = r + 1) {
r = min(n / (n / l), m / (m / l));
(ans += abss(g[r] - g[l - 1]) * 1ll * (n / l) % mod * (m / l) % mod) %= mod;
}
ans = (ans % mod + mod) % mod;
cout << ans << '\n';
}
return 0;
}
原文链接:https://www.cnblogs.com/loceaner/p/12785174.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:抽象宠物类的实现 代码参考
下一篇:STL之deque
- 【BZOJ2693】jzptab(莫比乌斯反演) 2019-08-26
- 二项式反演/minmax容斥初探 2019-08-16
- BZOJ2818: Gcd(莫比乌斯反演) 2018-07-20
- BZOJ4804: 欧拉心算(莫比乌斯反演 线性筛) 2018-07-20
- BZOJ4407: 于神之怒加强版(莫比乌斯反演 线性筛) 2018-07-19
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash