\(\sum_{i=1}^n\sum_{j=1}^m[s(\gcd(i,j))\le a]s(\gcd(i,j))\)
\(=\sum_{p=1}^ns(p)[s(p)\le a]\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=p]\)
\(=\sum_{p=1}^ns(p)[s(p)\le a]\sum_{i=1}^{n/p}\sum_{j=1}^{m/p}[\gcd(i,j)=1]\)
\(=\sum_{p=1}^ns(p)[s(p)\le a]\sum_{i=1}^{n/p}\sum_{j=1}^{m/p}\sum_{d|i,d|j}\mu(d)\)
\(=\sum_{p=1}^ns(p)[s(p)\le a]\sum_{d=1}^n\mu(d)\lfloor\frac n{pd}\rfloor\lfloor\frac m{pd}\rfloor\)
\(=\sum_{q=1}^n\sum_{p|q}s(p)[s(p)\le a]\mu(\frac q p)\lfloor\frac n{pd}\rfloor\lfloor\frac m{pd}\rfloor\)
离线，将询问按照\(a\)排序
由于前面最多只有nlogn个，可以线性筛之后都存一下，存一个三元组(p, s(p), 那一大坨子)，按照s(p)排序
离线处理询问，往树状数组里插值就行了，每次相当于在树状数组里查询前缀和之差，和普通的整除分块没什么太大的区别
#include#include #include using namespace std;struct query{ int n, m, a, id, ans;} ask[20010];struct info{ int val, id;} inf[100010];int q;bool vis[100010];int d[100010], d1[100010], mu[100010], prime[100000], tot, fuck = 100000;int c[100010];void chenge(int x, int y){ for (int i = x; i <= fuck; i += i & -i) c[i] += y;}int getsum(int x){ int ans = 0; for (int i = x; i > 0; i -= i & -i) ans += c[i]; return ans;}void add(int p){ for (int q = p, dd = 1; q <= fuck; q += p, dd++) chenge(q, d[p] * mu[dd]);}int main(){ scanf("%d", &q); for (int i = 1; i <= q; i++) { scanf("%d%d%d", &ask[i].n, &ask[i].m, &ask[i].a); ask[i].id = i; } sort(ask + 1, ask + 1 + q, [](const query &a, const query &b) { return a.a < b.a; }); mu[1] = d[1] = d1[1] = 1; for (int i = 2; i <= fuck; i++) { if (vis[i] == false) prime[++tot] = i, mu[i] = -1, d[i] = d1[i] = i + 1; for (int j = 1; j <= tot && i * prime[j] <= fuck; j++) { vis[i * prime[j]] = true; if (i % prime[j] == 0) { d1[i * prime[j]] = d1[i] * prime[j] + 1; d[i *prime[j]] = d[i] / d1[i] * d1[i * prime[j]]; break; } d1[i * prime[j]] = prime[j] + 1; d[i * prime[j]] = d[i] * (prime[j] + 1); mu[i * prime[j]] = -mu[i]; } } for (int i = 1; i <= fuck; i++) inf[i].id = i, inf[i].val = d[i]; sort(inf + 1, inf + 1 + fuck, [](const info &a, const info &b) { return a.val < b.val; }); for (int i = 1, j = 1; i <= q; i++) { while (j <= fuck && inf[j].val <= ask[i].a) { add(inf[j].id), j++; } int n = ask[i].n, m = ask[i].m; if (n > m) swap(n, m); int ans = 0; for (int i = 1, j; i <= n; i = j + 1) { j = min(n / (n / i), m / (m / i)); ans += (getsum(j) - getsum(i - 1)) * (n / i) * (m / i); } ask[i].ans = ans; } sort(ask + 1, ask + 1 + q, [](const query &a, const query &b) { return a.id < b.id; }); for (int i = 1; i <= q; i++) printf("%d\n", ask[i].ans & 2147483647); return 0;}
题目要求对2^31取模，别忘了自然溢出最后对2147483647取一下and