\[\operatorname{if(n}= 1) \sum_{d|n}\mu(d)=1
\]
\[\operatorname{if(n}\neq 1) \sum_{d|n}\mu(d)=0
\]
\[\mu * 1=\varepsilon
\]
\[\sum_{d|n}\mu(d)=\varepsilon(n)
\]
\[\sum_{d|n}\dfrac{\mu(d)}{d}=\dfrac{\varphi(n)}{n}
\]
\[\varphi(n)=\sum_{d|n}d\cdot\mu(\dfrac{n}{d})
\]
\[[\gcd(i,j)=1]=\sum_{d|\gcd(i,j)}\mu(d)
\]
\[\varphi(ij)=\dfrac{\varphi(i)\varphi(j)\gcd(i,j)}{\varphi(\gcd(i,j))}
\]
\[\mu(ij)=\mu(i)\mu(j)[\gcd(i,j)=1]
\]
\[\mu(\operatorname{lcm}(i,j))=\mu(i)\mu(j)\mu(\gcd(i,j))
\]
莫比乌斯反演
现有 \(f(n),g(n)\) 两个数论函数。
如果有
\[f(n)=\sum_{d|n}g(d)
\]
那么可以得出
\[g(n)=\sum_{d|n}\mu(d)f(\dfrac{n}{d})
\]
「HAOI 2011」Problem b
给出 \(x,y,n,m,k\) 。求
\[\sum_{i=x}^n\sum_{j=y}^m[\gcd(i,j)=k]
\]
\[\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=k]
\]
\[\sum_{i=1}^{\frac{n}{k}}\sum_{j=1}^{\frac{m}{k}}[\gcd(i,j)=1]
\]
\[\sum_{i=1}^{\frac{n}{k}}\sum_{j=1}^{\frac{m}{k}}[\gcd(i,j)=1]
\]
\[\sum_{i=1}^{\frac{n}{k}}\sum_{j=1}^{\frac{m}{k}}\sum_{d|\gcd(i,j)}\mu(d)
\]
\[\sum_{d=1}^{\min(\frac{n}{k},\frac{m}{k})}\mu(d)\sum_{i=1}^{\frac{n}{k}}[d|i]\sum_{j=1}^{\frac{m}{k}}[d|j]
\]
\[\sum_{d=1}^{\min(\frac{n}{k},\frac{m}{k})}\mu(d)\sum_{i=1}^{\frac{n}{k}}[d|i]\lfloor\dfrac{m}{dk}\rfloor
\]
\[\sum_{d=1}^{\min(\frac{n}{k},\frac{m}{k})}\mu(d)\lfloor\dfrac{n}{dk}\rfloor\lfloor\dfrac{m}{dk}\rfloor
\]
整除分块即可。
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
const int MAXN = 1e5 + 5;
bool vis[MAXN];
int len, mu[MAXN], prime[MAXN];
void Getmu() {
mu[1] = 1;
for (int i = 2; i < MAXN; i++) {
if (!vis[i])
prime[++len] = i, mu[i] = - 1;
for (int j = 1; j <= len && i * prime[j] < MAXN; j++) {
vis[i * prime[j]] = 1;
if (i % prime[j] == 0) {
mu[i * prime[j]] = 0;
break;
}
mu[i * prime[j]] = - mu[i];
}
}
for (int i = 2; i < MAXN; i++) mu[i] += mu[i - 1];
}
int T,n,m,x,y,k;
LL calc(int n,int m){
LL ans=0;
for(int i=1,j;i<=min(n/k,m/k);i=j+1){
j=min(n/(n/i),m/(m/i));
ans+=(mu[j]-mu[i-1])*(n/(i*k))*(m/(i*k));
}
return ans;
}
int main() {
Getmu();
int T;
scanf("%d",&T);
while(T--){
scanf("%d %d %d %d %d",&n,&m,&x,&y,&k);
printf("%d\n",calc(m,y)-calc(m,x-1)-calc(n-1,y)+calc(n-1,x-1));
}
return 0;
}
gcd求和¶
莫比乌斯反演入门好题 \(QAQ\) 。
\(T\) 次询问，每次询问给出 \(n,m\) 。求
\[\sum_{i=1}^n\sum_{j=1}^m\gcd(i,j)
\]
\[\sum_{d=1}^{\min(n,m)}d\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=d]
\]
\[\sum_{d=1}^{\min(n,m)}d\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}[\gcd(i,j)=1]
\]
\[\sum_{d=1}^{\min(n,m)}d\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}\sum_{D|\gcd(i,j)}\mu(D)
\]
然后再枚举一下 \(\gcd(i,j)\) ，并把 \(d\) 放进里面去。
\[\sum_{d=1}^{\min(n,m)}\sum_{D=1}^{\lfloor\frac{n}{d}\rfloor}d\cdot\mu(D)\lfloor\frac{n}{dD}\rfloor\lfloor\frac{m}{dD}\rfloor
\]
其实在这里已经可以做了，但是每次询问是 \(\mathcal{O(n+m)}\) ，于是尝试优化成 \(\mathcal{O(\sqrt{\min(n,m)})}\) 。
但是这个式子不好优化，考虑枚举 \(dD\) ，直接设为 \(T\) 。
\[\sum_{T=1}^{\min(n,m)}\sum_{d|T}d\cdot\mu(\dfrac{T}{d})\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor
\]
发现 \(\sum_{d|T}d\cdot\mu(\dfrac{T}{d})\) 这一堆就是 \(\varphi(T)\) （上面列出了这个式子的）。
所以可以推出
\[\sum_{T=1}^{\min(n,m)}\varphi(T)\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor
\]
直接整除分块即可，至此我们得到了 \(\mathcal{O(n)}\) 预处理，每次询问 \(\mathcal{O(\sqrt{\min(n,m)})}\) 的算法。
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 19, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 19], *p1 = buf, *p2 = buf;
LL read() {
LL ret = 0, f = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-')
f = -1;
ch = getchar();
}
for (; isdigit(ch); ch = getchar()) ret = ret * 10 + ch - 48;
return ret * f;
}
const int MAXN = 1e7 + 5;
bool vis[MAXN];
LL n, m, len, phi[MAXN], prime[MAXN], f[MAXN], low[MAXN], cnt[MAXN];
void seive1() {
phi[1] = 1;
for (int i = 2; i < MAXN; i++) {
if (!vis[i])
prime[++len] = i, phi[i] = i - 1;
for (int j = 1; j <= len && i * prime[j] < MAXN; j++) {
vis[i * prime[j]] = 1;
if (i % prime[j] == 0) {
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
phi[i * prime[j]] = phi[i] * (prime[j] - 1);
}
}
for (int i = 1; i < MAXN; i++) phi[i] += phi[i - 1];
}
void seive2() {
low[1] = f[1] = 1;
for (int i = 2; i < MAXN; i++) {
if (!vis[i])
prime[++len] = low[i] = i, f[i] = 2 * i - 1, cnt[i] = 1;
for (int j = 1; j <= len && i * prime[j] < MAXN; j++) {
vis[i * prime[j]] = 1;
if (i % prime[j] == 0) {
low[i * prime[j]] = low[i] * prime[j];
if (low[i] == i)
cnt[i * prime[j]] = cnt[i] + 1,
f[i * prime[j]] = (cnt[i * prime[j]] + 1) * i * prime[j] - cnt[i * prime[j]] * i;
else
f[i * prime[j]] = f[i / low[i]] * f[low[i] * prime[j]];
break;
}
low[i * prime[j]] = prime[j];
f[i * prime[j]] = f[i] * f[prime[j]];
}
}
for (int i = 2; i < MAXN; i++) f[i] = 2 * f[i] - i, f[i] += f[i - 1];
}
LL calc(LL n, LL m) {
LL ans = 0, l, r;
for (l = 1; l <= min(n, m); l = r + 1) {
r = min(n / (n / l), m / (m / l));
ans += (phi[r] - phi[l - 1]) * (n / l) * (m / l);
}
return ans;
}
int type, t;
int main() {
type = read(), t = read();
if (type >= 4 && type <= 7) {
seive2();
while (t--) {
n = read(), m = read();
printf("%lld\n", f[n]);
}
} else {
seive1();
while (t--) {
n = read(), m = read();
printf("%lld\n", calc(n, m));
}
}
return 0;
}
「BZOJ 2154」Crash 的数字表格¶
给出 \(n,m\) 。求
\[\sum_{i=1}^n\sum_{j=1}^m\operatorname{lcm}(i,j)
\]
首先，肯定要把 \(\operatorname{lcm(i,j)}\) 搞掉。
\[\sum_{i=1}^n\sum_{j=1}^m\dfrac{ij}{\gcd(i,j)}
\]
\[\sum_{d=1}^{\min(n,m)}\dfrac{1}{d}\sum_{i=1}^{n}\sum_{j=1}^{m}ij[\gcd(i,j)=d]
\]
\[\sum_{d=1}^{\min(n,m)}\dfrac{1}{d}\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}ijd^2[\gcd(i,j)=1]
\]
这里解释一下为什么后面还会多个 \(d^2\) ，因为你在砍掉 \(d\) 这个因子的时候， \(ij\) 的贡献就被砍掉了 \(d^2\) ，所以要补上。
\[\sum_{d=1}^{\min(n,m)}d\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}ij[\gcd(i,j)=1]
\]
后面那一坨很恶心，把后面那一坨搞出来。
设
\[f(n,m)=\sum_{i=1}^n\sum_{j=1}^mij[\gcd(i,j)=1]
\]
来一波反演。
\[f(n,m)=\sum_{i=1}^n\sum_{j=1}^mij\sum_{d|\gcd(i,j)}\mu(d)
\]
\[f(n,m)=\sum_{d=1}^{\min(n,m)}\mu(d)\sum_{i=1}^n\sum_{j=1}^mij[d|i][d|j]
\]
感觉还是不是很好做。于是决定改变枚举的对象
\[f(n,m)=\sum_{d=1}^{\min(n,m)}\mu(d)\sum_{i=1}^{id\le n}\sum_{j=1}^{jd\le m}ijd^2
\]
\[f(n,m)=\sum_{d=1}^{\min(n,m)}\mu(d)\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}ijd^2
\]
把 \(d^2\) 搞出来。
\[f(n,m)=\sum_{d=1}^{\min(n,m)}\mu(d)d^2\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}ij
\]
发现后面就是一个等差数列求和。
\[f(n,m)=\sum_{d=1}^{\min(n,m)}\mu(d)d^2\frac{(1+\frac{n}{d})\frac{n}{d}}{2}\frac{(1+\frac{m}{d})\frac{m}{d}}{2}
\]
于是 \(f(n,m)\) 就解决了。重新回到上面来。
\[\sum_{d=1}^{\min(n,m)}df(\frac{n}{d},\frac{m}{d})
\]
发现 \(f(n,m)\) 可以数论分块，于是数论分块套数论分块即可，但是这无法支持多次询问，一次询问就是 \(\mathcal{O(n+m)}\) 。我写的代码有点卡常数。
不开 \(\operatorname{long long}\) 见祖宗！
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
const int MAXN = 1e7 + 5;
LL mod = 20101009;
bool vis[MAXN];
int len, mu[MAXN], prime[MAXN];
LL s[MAXN];
void Getmu() {
mu[1] = 1;
for (int i = 2; i < MAXN; i++) {
if (!vis[i])
prime[++len] = i, mu[i] = -1;
for (int j = 1; j <= len && i * prime[j] < MAXN; j++) {
vis[i * prime[j]] = 1;
if (i % prime[j] == 0) {
mu[i * prime[j]] = 0;
break;
}
mu[i * prime[j]] = -mu[i];
}
}
}
LL Calc(int n, int m) {
LL ans = 0;
for (LL i = 1, j; i <= min(n, m); i = j + 1) {
j = min(n / (n / i), m / (m / i));
ans += ((s[j] - s[i - 1]) % mod) *
(((1 + n / i) * (n / i) / 2 % mod) * ((1 + m / i) * (m / i) / 2 % mod) % mod) % mod;
ans %= mod;
}
return ans;
}
LL calc(int n, int m) {
LL ans = 0;
for (LL i = 1, j; i <= min(n, m); i = j + 1) {
j = min(n / (n / i), m / (m / i));
ans += (((j - i + 1) * (i + j) / 2 % mod) * Calc(n / i, m / i)) % mod;
}
return ans;
}
int n, m;
int main() {
Getmu();
scanf("%d %d", &n, &m);
for (LL i = 1; i < MAXN; i++) s[i] = s[i - 1] + (i * i * mu[i] % mod), s[i] %= mod;
printf("%lld\n", (calc(n, m) % mod + mod) % mod);
return 0;
}
如果我们想要的得到更优的算法，怎么办呢？
想到可以跟上面的 \(\operatorname{gcd}\) 求和 一样改变枚举对象。
\[\sum_{d=1}^{\min(n,m)}\sum_{D=1}^{\min(\frac{n}{d},\frac{m}{d})}\mu(D)dD^2\frac{(1+\frac{n}{Dd})\frac{n}{Dd}}{2}\frac{(1+\frac{m}{Dd})\frac{m}{Dd}}{2}
\]
于是枚举一个 \(T=Dd\) 。
\[\sum_{T=1}^{\min(n,m)}\sum_{d|T}\mu(d)dT\dfrac{(1+\frac{n}{T})\frac{n}{T}}{2}\dfrac{(1+\frac{m}{T})\frac{m}{T}}{2}
\]
\[\sum_{T=1}^{\min(n,m)}\dfrac{(1+\frac{n}{T})\frac{n}{T}}{2}\dfrac{(1+\frac{m}{T})\frac{m}{T}}{2}\sum_{d|T}\mu(d)dT
\]
发现 \(\sum_{d|T}\mu(d)dT\) 是一个积性函数，为什么呢？
这里补充一下积性函数的知识。
如果两个函数 \(f(x)\) 与 \(g(x)\) 都是积性函数，那么一下函数都是积性函数：
\[h(x)=f(x^p)
\]
\[h(x)=f^p(x)
\]
\[h(x)=f(x)g(x)
\]
\[h(x)=\sum_{d|x}f(d)f(\dfrac{x}{d})
\]
可以发现 \(\sum_{d|T}\mu(d)dT\) 满足第四条。于是可以直接线性筛，然后对 \(T\) 数论分块即可。
单次询问时间复杂度 \(\mathcal{O(\sqrt{\min(n,m)})}\) 。
设 \(q(x)=\sum_{d|x}\mu(d)dT\) ，\(w(x)=\sum_{d|x}\mu(d)d\) 。
可以得到
\[w(\operatorname{prime}^p)=1-\operatorname{prime}
\]
然后线性筛 \(q(x)\) 即可。
代码就不放了。
「SDOI2015」约数个数和
给出 \(n,m\) 。求
\[\sum_{i=1}^n\sum_{j=1}^m d(ij)
\]
其 \(d(x)\) 表示数 \(x\) 的约数个数。
这个题很妙啊， \(d(ij)\) 有一个特殊性质。
\[d(ij)=\sum_{x|i}\sum_{y|j}[\gcd(x,y)=1]
\]
代进原式可得
\[\sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j}[\gcd(x,y)=1]
\]
跟原来一样的套路，莫比乌斯反演一下。
\[\sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j}\sum_{d|\gcd(x,y)}\mu(d)
\]
但是这样并不好做，考虑先交换和式顺序。
\[\sum_{x=1}^n\sum_{y=1}^m\sum_{i=1}^{ix\le n}\sum_{j=1}^{jy\le m}[\gcd(x,y)=1]
\]
\[\sum_{x=1}^n\sum_{y=1}^m\sum_{i=1}^{ix\le n}\sum_{j=1}^{jy\le m}[\gcd(x,y)=1]
\]
\[\sum_{x=1}^n\sum_{y=1}^m\sum_{i=1}^{\frac{n}{x}}\sum_{j=1}^{\frac{m}{y}}[\gcd(x,y)=1]
\]
\[\sum_{x=1}^n\sum_{y=1}^m\lfloor\dfrac{n}{x}\rfloor\lfloor\dfrac{m}{y}\rfloor[\gcd(x,y)=1]
\]
\[\sum_{x=1}^n\sum_{y=1}^m\lfloor\dfrac{n}{x}\rfloor\lfloor\dfrac{m}{y}\rfloor\sum_{d|\gcd(x,y)}\mu(d)
\]
\[\sum_{d=1}^{\min(n,m)}\mu(d)\sum_{x=1}^n[d|x]\sum_{y=1}^m[d|y]\lfloor\dfrac{n}{x}\rfloor\lfloor\dfrac{m}{y}\rfloor
\]
\[\sum_{d=1}^{\min(n,m)}\mu(d)\sum_{x=1}^{\frac{n}{d}}\sum_{y=1}^{\frac{m}{d}}\lfloor\dfrac{n}{xd}\rfloor\lfloor\dfrac{m}{yd}\rfloor$
$$\sum_{d=1}^{\min(n,m)}\mu(d)\sum_{x=1}^{\frac{n}{d}}\lfloor\dfrac{n}{xd}\rfloor\sum_{y=1}^{\frac{m}{d}}\lfloor\dfrac{m}{yd}\rfloor\]
后面那两坨形式是一样的，直接整除分块预处理即可，然后对 \(d\) 整除分块即可。
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
const int MAXN = 5e4 + 5;
LL mod = 20101009;
bool vis[MAXN];
int len, prime[MAXN];
LL s[MAXN], mu[MAXN];
void Getmu() {
mu[1] = 1;
for (int i = 2; i < MAXN; i++) {
if (!vis[i])
prime[++len] = i, mu[i] = -1;
for (int j = 1; j <= len && i * prime[j] < MAXN; j++) {
vis[i * prime[j]] = 1;
if (i % prime[j] == 0) {
mu[i * prime[j]] = 0;
break;
}
mu[i * prime[j]] = -mu[i];
}
}
for (int i = 2; i < MAXN; i++) mu[i] += mu[i - 1];
for (int k = 1; k < MAXN; k++) {
for (int i = 1, j; i <= k; i = j + 1) {
j = k / (k / i);
s[k] += (j - i + 1) * (k / i);
}
}
}
LL calc(LL n, LL m) {
LL ans = 0;
for (LL i = 1, j; i <= min(n, m); i = j + 1) {
j = min(n / (n / i), m / (m / i));
ans += (mu[j] - mu[i - 1]) * s[n / i] * s[m / i];
}
return ans;
}
LL n, m;
signed main() {
int T;
scanf("%d", &T);
Getmu();
while (T--) {
scanf("%lld %lld", &n, &m);
printf("%lld\n", calc(n, m));
}
return 0;
}
「LuoGu P2257」YY的GCD
\(T\) 次询问，每次询问给出 \(n,m\) 。求
\[\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)\in\operatorname{Prime}]
\]
\[\sum_{d=1}^{\min(n,m)}[d\in\operatorname{Prime}]\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=d]
\]
\[\sum_{d=1}^{\min(n,m)}[d\in\operatorname{Prime}]\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}[\gcd(i,j)=1]
\]
\[\sum_{d=1}^{\min(n,m)}[d\in\operatorname{Prime}]\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}[\gcd(i,j)=1]
\]
\[\sum_{d=1}^{\min(n,m)}[d\in\operatorname{Prime}]\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}\sum_{D|\gcd(i,j)}\mu(D)
\]
\[\sum_{d=1}^{\min(n,m)}[d\in\operatorname{Prime}]\sum_{D=1}^{\min(\frac{n}{d},\frac{m}{d})}\mu(D)\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}[D|i][D|j]
\]
\[\sum_{d=1}^{\min(n,m)}[d\in\operatorname{Prime}]\sum_{D=1}^{\min(\frac{n}{d},\frac{m}{d})}\mu(D)\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}[D|i][D|j]
\]
\[\sum_{d=1}^{\min(n,m)}[d\in\operatorname{Prime}]\sum_{D=1}^{\min(\frac{n}{d},\frac{m}{d})}\mu(D)\lfloor\dfrac{n}{dD}\rfloor\lfloor\dfrac{m}{dD}\rfloor
\]
老套路，改变枚举对象，枚举 \(T=dD\) 。
\[\sum_{T=1}^{\min(n,m)}\sum_{d|T}[d\in\operatorname{Prime}]\lfloor\dfrac{n}{T}\rfloor\lfloor\dfrac{m}{T}\rfloor\mu(\dfrac{T}{d})
\]
\[\sum_{T=1}^{\min(n,m)}\lfloor\dfrac{n}{T}\rfloor\lfloor\dfrac{m}{T}\rfloor\sum_{d|T}[d\in\operatorname{Prime}]\mu(\dfrac{T}{d})
\]
题目给了 \(4s\) ，后面那一坨直接预处理即可。
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
const int MAXN = 1e7 + 5;
bool vis[MAXN];
int len, prime[MAXN];
LL s[MAXN], mu[MAXN];
void Getmu() {
mu[1] = 1;
for (int i = 2; i < MAXN; i++) {
if (!vis[i])
prime[++len] = i, mu[i] = -1;
for (int j = 1; j <= len && i * prime[j] < MAXN; j++) {
vis[i * prime[j]] = 1;
if (i % prime[j] == 0) {
mu[i * prime[j]] = 0;
break;
}
mu[i * prime[j]] = -mu[i];
}
}
for (int i = 1; i <= len; i++)
for (int j = 1; j * prime[i] <= MAXN - 5; j++) s[j * prime[i]] += mu[j];
for (int i = 1; i <= MAXN - 5; i++) s[i] += s[i - 1];
}
LL calc(int n, int m) {
LL ans = 0;
int mmp = min(n, m);
for (LL i = 1, j; i <= mmp; i = j + 1) {
LL mmp1 = n / i, mmp2 = m / i;
j = min(n / mmp1, m / mmp2);
ans += (s[j] - s[i - 1]) * mmp1 * mmp2;
}
return ans;
}
int n, m;
signed main() {
int T;
scanf("%d", &T);
Getmu();
while (T--) {
scanf("%d %d", &n, &m);
printf("%lld\n", calc(n, m));
}
return 0;
}
「NOI 2010」能量采集
好水啊 \(QAQ\) 。
给出 \(n,m\) 。求
\[2\sum_{i=1}^n\sum_{j=1}^m\gcd(i,j)-n\times m
\]
把上面的 \(\operatorname{gcd}\) 求和套一下就好了。
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 19, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 19], *p1 = buf, *p2 = buf;
LL read() {
LL ret = 0, f = 1;
char ch = getchar();
while (!isdigit(ch)) {
if (ch == '-')
f = -1;
ch = getchar();
}
for (; isdigit(ch); ch = getchar()) ret = ret * 10 + ch - 48;
return ret * f;
}
const int MAXN = 1e7 + 5;
bool vis[MAXN];
LL n, m, len, phi[MAXN], prime[MAXN], f[MAXN], low[MAXN], cnt[MAXN];
void seive1() {
phi[1] = 1;
for (int i = 2; i < MAXN; i++) {
if (!vis[i])
prime[++len] = i, phi[i] = i - 1;
for (int j = 1; j <= len && i * prime[j] < MAXN; j++) {
vis[i * prime[j]] = 1;
if (i % prime[j] == 0) {
phi[i * prime[j]] = phi[i] * prime[j];
break;
}
phi[i * prime[j]] = phi[i] * (prime[j] - 1);
}
}
for (int i = 1; i < MAXN; i++) phi[i] += phi[i - 1];
}
void seive2() {
low[1] = f[1] = 1;
for (int i = 2; i < MAXN; i++) {
if (!vis[i])
prime[++len] = low[i] = i, f[i] = 2 * i - 1, cnt[i] = 1;
for (int j = 1; j <= len && i * prime[j] < MAXN; j++) {
vis[i * prime[j]] = 1;
if (i % prime[j] == 0) {
low[i * prime[j]] = low[i] * prime[j];
if (low[i] == i)
cnt[i * prime[j]] = cnt[i] + 1,
f[i * prime[j]] = (cnt[i * prime[j]] + 1) * i * prime[j] - cnt[i * prime[j]] * i;
else
f[i * prime[j]] = f[i / low[i]] * f[low[i] * prime[j]];
break;
}
low[i * prime[j]] = prime[j];
f[i * prime[j]] = f[i] * f[prime[j]];
}
}
for (int i = 2; i < MAXN; i++) f[i] = 2 * f[i] - i, f[i] += f[i - 1];
}
LL calc(LL n, LL m) {
LL ans = 0, l, r;
for (l = 1; l <= min(n, m); l = r + 1) {
r = min(n / (n / l), m / (m / l));
ans += (phi[r] - phi[l - 1]) * (n / l) * (m / l);
}
return ans;
}
int type, t;
int main() {
seive1();
n = read(), m = read();
printf("%lld\n", 2 * calc(n, m) - n * m);
return 0;
}
「SDOI2017」数字表格
好难啊。
\(T\) 次询问，每次询问给出 \(n,m\) 。求
\[f_0=0,f_1=1,f_i=f_{i-1}+f_{i-2}
\]
\[\prod_{i=1}^n\prod_{j=1}^mf_{\gcd(i,j)}
\]
\[\prod_{d=1}^{\min(n,m)}f_d^{\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=d]}
\]
\[\prod_{d=1}^{\min(n,m)}f_d^{\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}[\gcd(i,j)=1]}
\]
把指数给提出来，指数太恶心了。
\[\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}[\gcd(i,j)=1]
\]
\[\sum_{i=1}^{\frac{n}{d}}\sum_{j=1}^{\frac{m}{d}}\sum_{D|\gcd(i,j)}\mu(D)
\]
\[\sum_{D=1}^{\min(\frac{n}{d},\frac{m}{d})}\mu(D)\sum_{i=1}^{\frac{n}{d}}[D|i]\sum_{j=1}^{\frac{m}{d}}[D|j]
\]
\[\sum_{D=1}^{\min(\frac{n}{d},\frac{m}{d})}\mu(D)\lfloor\dfrac{n}{dD}\rfloor\lfloor\dfrac{m}{dD}\rfloor
\]
老套路，设 \(T=dD\) ，代回原式。
\[\prod_{T=1}^{\min(n,m)}\prod_{d|T}f_d^{\mu(\frac{T}{d})\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor}
\]
\[\prod_{T=1}^{\min(n,m)}(\prod_{d|T}f_d^{\mu(\frac{T}{d})})^{{\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor}}
\]
#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
#define LL long long
const int MAXN = 1e6 + 5;
bool vis[MAXN];
int len, mu[MAXN], prime[MAXN];
LL f1[MAXN], f2[MAXN], s[MAXN];
const LL mod = 1e9 + 7;
LL qkpow(LL x, LL power, LL mod) {
x %= mod;
LL ans = 1;
for (; power; power >>= 1, (x *= x) %= mod)
if (power & 1)
(ans *= x) %= mod;
return ans;
}
void Getmu() {
mu[1] = 1;
f1[1] = 1, f2[1] = 1;
s[0] = s[1] = 1;
for (int i = 2; i < MAXN; i++) {
f1[i] = (f1[i - 1] + f1[i - 2]) % mod;
f2[i] = qkpow(f1[i], mod - 2, mod);
s[i] = 1;
if (!vis[i])
prime[++len] = i, mu[i] = -1;
for (int j = 1; j <= len && i * prime[j] < MAXN; j++) {
vis[i * prime[j]] = 1;
if (i % prime[j] == 0) {
mu[i * prime[j]] = 0;
break;
}
mu[i * prime[j]] = -mu[i];
}
}
for (int i = 1; i <= MAXN - 5; i++) {
if (!mu[i])
continue;
for (int j = i; j <= MAXN - 5; j += i) s[j] = s[j] * (mu[i] == 1 ? f1[j / i] : f2[j / i]) % mod;
}
for (int i = 1; i < MAXN; i++) s[i] = s[i] * s[i - 1] % mod;
}
int T;
LL n, m;
LL calc(LL n, LL m) {
LL ans = 1;
for (LL i = 1, j; i <= min(n, m); i = j + 1) {
j = min(n / (n / i), m / (m / i));
ans = ans * qkpow(s[j] % mod * qkpow(s[i - 1], mod - 2, mod), (n / i) * (m / i), mod) % mod;
}
return ans;
}
int main() {
Getmu();
scanf("%d", &T);
while (T--) {
scanf("%lld %lld", &n, &m);
printf("%lld\n", calc(n, m));
}
return 0;
}
括号里面的直接整除分块就好了。