较简单的容斥
题目大意：
设 g(x) 为莫比乌斯函数的绝对值，把 g(1)g(2)g(3)…g(n) 连起来看成一个10进制数，其中 g(1) 是最高位，那么这个数是多少。
解题思路：
正难则反，我们可以先考虑所有位是 1 ，再刨除 g(i)=0 的位置。
- 计算所有位是 1 的n位数对 1000000007 取模
S(n)=\frac{10^n-1}{9}
- 计算 g(i)=0 的位置贡献的值
由 g(x) 的定义，我们可以看出所有 2^2,3^2,…,k^2(k^2\leq n) 的倍数要被刨除。对于 k^2，我们要刨除的总和：
由于 g(k^2),g(2k^2)…从高位向地位排列，因此这是一个以 10^{n-k^2} 为首项、10^{-k^2} 为公比、\left\lfloor\frac{n}{k^2}\right\rfloor 为项数的等比数列。因此，
S(k)=\frac{10^{n-k^2}(1-10^{-k^2 * \left\lfloor\frac{n}{k^2}\right\rfloor})}{1-10^{-k^2}}
- 用容斥原理排除重复计算
对于每个S(k)，在计算其每个因子时均计算了一次k，因此应当用莫比乌斯函数作为容斥系数。 -
得到答案
$$
ans=\frac{10^n-1}{9}+\sum_{k=2}^{k^2\leq n}\mu(k)\cdot\frac{10^{n-k^2}(1-10^{-k^2 * \left\lfloor\frac{n}{k^2}\right\rfloor})}{1-10^{-k^2}}
$$
#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int P = 1e9 + 7;
const int N = 1e6 + 10;
ll n;
int prime[N], num[N], mu[N], tot;
void getmu() {
mu[1] = 1;
for (int i = 2; i < N; i++) {
if (!num[i]) {
prime[++tot] = i;
mu[i] = -1;
}
for (int j = 1, x; j <= tot && (x = i * prime[j]) < N; j++) {
num[x] = 1;
if (i % prime[j]) mu[x] = -mu[i];
else break;
}
}
}
int ksm(int a, ll b) {
int ret = 1;
for (; b; b >>= 1, a = 1LL * a * a % P) {
if (b & 1) {
ret = 1LL * ret * a % P;
}
}
return ret;
}
int ni(int a) {
return ksm(a, P - 2);
}
int main() {
scanf("%lld", &n);
ll ans = 1LL * (ksm(10, n) - 1) * ni(9) % P;
getmu();
for (ll i = 2; i * i <= n; i++) {
if (!mu[i]) continue;
int tmp1 = ni(ksm(10, i * i));
int tmp2 = 1LL * ksm(10, n) * tmp1 % P;
int tmp3 = 1LL * ksm(tmp1, n / (i * i)) % P - 1;
int sum = 1LL * tmp2 * tmp3 % P * ni(tmp1 - 1) % P;
ans += sum * mu[i];
}
((ans %= P) += P) %= P;
printf("%lld\n", ans);
return 0;
}
较复杂的容斥
题目大意：一个 (n,m,d) 好序列 (a_{1},a_{2},…,a_{n}) 当且仅当 1 \leq a_{i} \leq m(1 \le i \le n) 且 \gcd(a_{1},a_{2},\cdots,a_{n})=d 。定义 f((a_{1},a_{2},…a_{n}),k) = (a_{1}a_{2} \cdots a_{n})^{k} ，求 \sum f(q, k)，q 为好序列。
- step1
由于 \gcd(a_{1},a_{2},\cdots,a_{n})=d，因此我们可以将每个数提出一个d，在式子外面乘上一个 (d^k)^n。
剩下可选取的数：
\begin{bmatrix}\lfloor \frac{m}{d}\rfloor&\lfloor\frac{m}{d}\rfloor&…&\lfloor\frac{m}{d}\rfloor&\lfloor\frac{m}{d}\rfloor\cr …&…&…&…&… \cr 3&3&…&3&3\cr 2&2&…&2&2\cr 1&1&…&1&1 \end{bmatrix}
- step2
由分配律，
\sum(a_{1}a_{2} \cdots a_{n})^{k}=\bigg(\sum_{i=1}^{\lfloor \frac{m}{d}\rfloor}i^k\bigg)^n
- step3
考虑到 \gcd(a_{1},a_{2},\cdots,a_{n})\not= 1 的情况，我们容易发现这是一个和约数有关的容斥原理，每个数均被其所有约数计算过一次，即容斥系数应当是莫比乌斯函数！
对于 \gcd(a_{1},a_{2},\cdots,a_{n})= b, 剩下可选的数：
\begin{bmatrix}\lfloor \frac{m}{bd}\rfloor&\lfloor \frac{m}{bd}\rfloor&…&\lfloor \frac{m}{bd}\rfloor&\lfloor \frac{m}{bd}\rfloor\cr …&…&…&…&… \cr 3b&3b&…&3b&3b\cr2b&2b&…&2b&2b\cr b&b&…&b&b\cr \end{bmatrix}
\sum(a_{1}a_{2} \cdots a_{n})^{k}=\left(\bigg(\sum_{i=1}^{\lfloor \frac{m}{bd}\rfloor}i^k\bigg)b^k\right)^n
- step4
ans=(d^k)^n\sum_{i=1}^{\lfloor \frac{m}{d}\rfloor}\mu(i)\left(\bigg(\sum_{j=1}^{\lfloor \frac{m}{id}\rfloor}j^k\bigg)i^k\right)^n
我们注意到 n 只出现于指数上，由扩展欧拉定理，可以在读入 n 时对 \varphi(mod) 取模；对于每次询问，我们可以 O(m) 预处理出 k^1,k^2,…,k^m ，以及其前缀和。计算时，对于内层括号里的东西我们就可以O(1)求，再跑一个快速幂，总体复杂度 O(T * mlog_n)。
#include <bits/stdc++.h>
using namespace std;
const int P = 59964251;
const int phi = 59870352;
const int N = 1e5 + 50;
int T, n, m, d, k;
char s[N];
int maxup;
int powk[N], sumpowk[N];
int getmod(int mo) {
int b = 0; char c;
while(!isdigit(c = getchar()));
for(; isdigit(c); c = getchar()) {
b = b * 10 + c - '0';
if(b >= mo) b %= mo;
}
return b;
}
inline int add(int a, int b) {
int ret = a + b;
if (ret > P) ret -= P;
return ret;
}
int ksm(int a, int b) {
int ret = 1;
for (; b; b >>= 1, a = 1LL * a * a % P) {
if (b & 1) ret = 1LL * ret * a % P;
}
return ret;
}
int mu[N], prime[N], num[N], tot;
void pre() {
mu[1] = 1;
for (int i = 2; i < N; i++) {
if (!num[i]) {
prime[++tot] = i;
mu[i] = -1;
}
for (int j = 1, x; j <= tot && (x = i * prime[j]) < N; j++) {
num[x] = 1;
if(i % prime[j]) mu[x] = -mu[i];
else break;
}
}
}
void init() {
maxup = m / d;
for(int i = 1; i <= maxup; i++) powk[i] = ksm(i, k);
for(int i = 1; i <= maxup; i++) sumpowk[i] = add(sumpowk[i-1], powk[i]);
}
void work() {
int sum = 0;
for (int i = 1; i <= maxup; i++) {
int tmp1 = maxup / i;
int tmp2 = 1LL * sumpowk[tmp1] * powk[i] % P;
int tmp3 = ksm(tmp2, n);
(sum += P + tmp3 * mu[i]) %= P;
}
int b = 1LL * n * k % phi;
sum = 1LL * sum * ksm(d, b) % P;
printf("%d\n", sum);
}
int main() {
scanf("%d", &T);
pre();
while(T--) {
n = getmod(phi);
if(!n) n = phi;
scanf("%d%d%d", &m, &d, &k);
k %= phi;
if (!k) k = phi;
init(); work();
}
return 0;
}
巧妙判断互质数的数目
题目大意：
给n个数 a_1,a_2,\cdots ,a_n ，求
\max_{1\leq i\leq n}lcm\left(a_i,a_j\right)
问题分析：
枚举答案 a_i,a_j 的最大公约数 g。对于每个 g，我们取出所有 g 的倍数并都除以 g，按照从大到小排列。维护一个栈，元素从大到小依次入栈。对于当前遍历到的数 y，如果栈内存在一个 x 使得 gcd(x,y)=1 ，那么在当前这个 g 的条件下，所有 y\leq z\leq x 的 z 失去意义，从栈中弹出。
考虑如何判断栈中是否有数和 y 互质：由于一个数的 1 以外因子及其全部倍数都与其本身不互质，记 cnt_i 为栈中 i 倍数的个数，那么这就是一个以莫比乌斯函数为容斥系数的容斥定理，即与 y 互质数的个数：(也可用莫比乌斯反演得到)
\sum_{d|y}\mu(d) * cnt_d
我们可以预处理出所有数的全部因子。
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 50;
const int MAX = 1e5;
int n, a[N], b[N];
long long ans = 0;
int gcd(int a, int b) {
return b == 0 ? a : gcd(b, a % b);
}
vector<int> d[N];
int mu[N], used[N], prime[N], tot;
void init() {
// 线性筛mu部分略。以下为预处理全部因子。
for(int i = 1; i < N; i++) {
for(int j = i; j < N; j += i) {
d[j].push_back(i);
}
}
}
stack<int> s;
int cnt[N];
int coprime(int x) { // 返回栈中与x互质数的个数
int ret = 0;
for(int i : d[x]) ret += cnt[i] * mu[i];
return ret;
}
void update(int x, int v) { //栈中加入x，其全部因子的倍数个数加1。弹出栈同理
for (int i : d[x]) cnt[i] += v;
}
int main() {
n = read();
for(int i = 1; i <= n; i++) {
a[i] = read(); b[a[i]] = 1; // 离散化+去重
ans = max(ans, (long long)a[i]);
}
init();
for(int g = 1; g <= MAX; g++) {
int beg = MAX / g;
for (int i = beg; i; i--) {
if (!b[i * g]) continue;
int num = coprime(i);
while (num) {
if (gcd(s.top(), i) == 1) {
if (num == 1) ans = max(ans, 1LL * s.top() * i * g);
num--;
}
update(s.top(), -1); s.pop();
}
s.push(i); update(i, 1);
}
while (!s.empty()) {
update(s.top(), -1);
s.pop();
}
}
printf("%lld\n", ans);
return 0;
}