題意

給出 \(a,b,c,d,k\) ，求 \(\sum_{i=a}^b\sum_{j=c}^d[gcd(i,j)==k]\) 。

傳送

Luogu

BZOJ

分析

假設 \(b\le d\)

將 \(k\) 提出來

\[\sum_{i=a}^{\lfloor\frac{b}{k}\rfloor}\sum_{j=c}^{\lfloor\fracze8trgl8bvbq{k}\rfloor}[gcd(i,j)==1]\]

將 \(gcd(i,j)==1\) 替換為 \(\epsilon(gcd(i,j))\)

\[\sum_{i=a}^{\lfloor\frac{b}{k}\rfloor}\sum_{j=c}^{\lfloor\fracze8trgl8bvbq{k}\rfloor}\epsilon(gcd(i,j))\]

再將 \(\epsilon\) 函數用 \(\mu\) 表示

\[\sum_{i=a}^{\lfloor\frac{b}{k}\rfloor}\sum_{j=c}^{\lfloor\fracze8trgl8bvbq{k}\rfloor}\sum_{d|gcd(i,j)}\mu(d)\]

交換求和順序，改為枚舉 \(d\)

\[\sum_{d=1}^{\lfloor\frac{b}{k}\rfloor}\mu(d)\sum_{i=1}^{\lfloor\frac{b}{k}\rfloor}d|i\sum_{j=1}^{\lfloor\fracze8trgl8bvbq{k}\rfloor}d|j\]

\(\sum_{i=1}^{\lfloor\frac{b}{k}\rfloor}d|i\) 即 \({\lfloor\frac{b}{k}\rfloor}\) 以內 \(i\) 的約數個數和，等于 \(\lfloor\frac{b}{kd}\rfloor\) ，同理， \(\sum_{j=1}^{\lfloor\fracze8trgl8bvbq{k}\rfloor}d|j\) 等同于 \(\lfloor\fracze8trgl8bvbq{kd}\rfloor\) 。

則式子為

\[\sum_{d=1}^{\lfloor\frac{b}{k}\rfloor}\mu(d)\lfloor\frac{b}{kd}\rfloor\lfloor\fracze8trgl8bvbq{kd}\rfloor\]

于是我們便可以用整除分塊求解了。

代碼

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define N 500005
#define il inline
#define re register
#define tie0 cin.tie(0),cout.tie(0)
#define fastio ios::sync_with_stdio(false)
#define File(x) freopen(x".in","r",stdin);freopen(x".out","w",stdout)
using namespace std;
typedef long long ll;template <typename T> inline void read(T &x) {T f = 1; x = 0; char c;for (c = getchar(); !isdigit(c); c = getchar()) if (c == '-') f = -1;for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);x *= f;
}int a, b, c, d, k;
int mu[N], prime[N];
bool vis[N];void sieve() {int cnt = 0;mu[1] = 1;for (int i = 2; i <= N; ++i) {if (!vis[i]) prime[++cnt] = i, mu[i] = -1;for (int j = 1; j <= cnt && i * prime[j] <= N; ++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 <= N; ++i) mu[i] += mu[i-1];
}int f(int n, int m) {int sum = 0;for (int i = 1, j; i <= min(n, m); i = j + 1) {j = min(n / (n / i), m / (m / i));sum += (mu[j] - mu[i-1]) * (n / i) * (m / i);}return sum;
}int main() {int n;read(n);sieve();while (n--) {read(a), read(b), read(c), read(d), read(k);printf("%d\n", f(b / k, d / k) - f(b / k, (c - 1) / k) - f((a - 1) / k, d / k) + f((a - 1) / k, (c - 1) / k));}return 0;
}

轉載于:https://www.cnblogs.com/hlw1/p/11537360.html

總結

以上是生活随笔為你收集整理的HAOI2011 Problem b的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。