题目
题目描述
“我不知道你在说什么，因为我只是个pupil。”--绿魔法师
一个空的可重集合S。
n次操作，每次操作给出x,k,p，执行以下操作：
1、在S中加入x。
2、输出 \(\sum_{y \in S}{gcd(x,y)^k} (mod p)\) 。
输入描述
所有输入的数都是小于1e5+1的正整数。
输出描述
输出对应的结果
示例1
输入
3
4 1 9
5 2 8
6 3 7
输出
4
2
1
题解
知识点：因数集合，GCD与LCM，容斥原理，枚举。
每次插入一个数 \(x\) 时，因为 \(\gcd(y,x)\) 的值一定不会出现 \(x\) 因数之外的数，所以考虑枚举这个数的因数 \(d\) 作为 \(\gcd(x,y)\) 时的贡献，即有多少个 \(y\) 满足条件。
我们先预处理出数据范围内所有数的因数，用 \(cnt_d\) 表示整个集合中存在因数 \(d\) 的数的个数，方便之后计数。
因为是最大公约数，应该先考虑较大数的贡献，计算完较大数后，在计算较小数时应减去较大数的影响，所以我们从大到小枚举因数，同时对较小因数做一个容斥。
因此，每次加入一个数 \(x\) 时，用 \(tot_d\) 表示 \(gcd(y,x) = d\) 中 \(y\) 的个数，即 \(d\) 产生的贡献。那么， \(tot_d\) 应该等于 \(cnt_d\) 减去它所有是 \(x\) 的因数的倍数 \(d'\) 的贡献 \(tot_{d'}\) ，即 \(\displaystyle tot_d = cnt_d - \sum_{d \mid d',d'|x} tot_{d'}\) 。这个可以在我们遇到 \(d'\) 时对它的因数贡献减去 \(tot_{d'}\) 来维护。
最后，对于一个因数 \(d\) 产生的贡献为 \(tot_d \cdot d^k\) ，累和即可。
复杂度的上界确实是 \(O(n \max\{x\})\) ，但是跑不满，因为因数个数的上界 \(O(\sqrt {\max\{x\}})\) 是非常松的，这里的总计算量级差不多 \(10^8\) 。
时间复杂度 \(O(n \cdot \max\{x\})\)
空间复杂度 \(O(1)\)
代码
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
vector<int> factor[100007];
void get_factor(int n) {
for (int i = n;i >= 1;i--)
for (int j = 1;i * j <= n;j++)
factor[i * j].push_back(i);
}
int qpow(int a, int k, int P) {
int ans = 1;
while (k) {
if (k & 1) ans = 1LL * ans * a % P;
k >>= 1;
a = 1LL * a * a % P;
}
return ans;
}
int cnt[100007];//S中i的倍数的个数
int tot[100007];//gcd(x,y)=i的y的个数，通过容斥维护
int main() {
std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
get_factor(100000);
int n;
cin >> n;
for (int i = 1;i <= n;i++) {
int x, k, p;
cin >> x >> k >> p;
int ans = 0;
for (auto d : factor[x]) {
tot[d] += ++cnt[d];// 以d为gcd的个数 = d的倍数个数 - d的倍数作为gcd的数字个数
if (!tot[d]) continue;
(ans += 1LL * tot[d] * qpow(d, k, p) % p) %= p;
int tmp = tot[d];
for (auto dd : factor[d]) tot[dd] -= tmp; // 给dd减去的其倍数d作为gcd的数字个数
}
cout << ans << '\n';
}
return 0;
}