Problem b HYSBZ - 2301

对于给出的 $n$ 个询问，每次求有多少个数对 $(x,y)$ ，满足 $a\le x\le b$ ， $c\le y\le d$ ，且 $gcd(x,y)=k$ ， $gcd(x,y)$ 函数为 $x$ 和 $y$ 的最大公约数。

Input

第一行一个整数 $n$，接下来 $n$ 行每行五个整数，分别表示 $a、b、c、d、k$

Output

共 $n$ 行，每行一个整数表示满足要求的数对 $(x,y)$ 的个数

Sample Input

2
2 5 1 5 1
1 5 1 5 2

Sample Output

14
3

Hint

$100\%$ 的数据满足：$1\le n\le 50000，1\le a\le b\le 50000，1\le c\le d\le 50000，1\le k\le 50000$

题解

题目求解
$$\sum _{x=a}^b\sum _{y=c}^d[gcd(x,y)=k]$$

令 $f=[gcd(x,y)=k]$
根据容斥的原理，我们可以知道
$$\sum _{x=a}^b\sum _{y=c}^{d}f=\sum _{x=1}^b\sum _{y=1}^{d}f-\sum _{x=1}^{a-1}\sum _{y=1}^{d}f-\sum _{x=1}^b\sum _{y=1}^{c-1}f+\sum _{x=1}^{a-1}\sum _{y=1}^{c-1}f$$
所以重点在于 ${\sum }_{x=1}^n{\sum }_{y=1}^{m}f$ 的求法。
和以前一样，令 $n^{\prime }=\lfloor \frac{n}{k}\rfloor ,m^{\prime }=\lfloor \frac{m}{k}\rfloor$ 。
$$\begin{array}{rl}\sum _{x=1}^n\sum _{y=1}^m[gcd(x,y)=k]& =\sum _{x=1}^{n^{\prime }}\sum _{y=1}^{m^{\prime }}[gcd(x,y)=1]\\ & =\sum _{x=1}^{n^{\prime }}\sum _{y=1}^{m^{\prime }}\sum _{d|gcd(x,y)}\mu (d)\\ & =\sum _{d=1}^{min(n^{\prime },m^{\prime })}\mu (d)\ast \lfloor \frac{n^{\prime }}{d}\rfloor \ast \lfloor \frac{m^{\prime }}{d}\rfloor \end{array}$$
因此也可以分块计算。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 5e4 + 10;
int mu[maxn], prime[maxn], cnt = 0;
bool vis[maxn];

void init() {
    
  mu[1] = 1;
  for (int i = 2; i < maxn; i++) {
    
    if (vis[i] == false) {
    
      prime[cnt++] = i;
      mu[i] = -1;
    }
    for (int j = 0; j < cnt && i * prime[j] < maxn; j++) {
    
      vis[i * prime[j]] = true;
      if (i % prime[j] == 0) {
    
        mu[i * prime[j]] = 0;
        break;
      } else {
    
        mu[i * prime[j]] = -mu[i];
      }
    }
  }
  for (int i = 2; i < maxn; i++) {
    
    mu[i] += mu[i - 1];
  }
}

int solve(int a, int b) {
    
  int ans = 0;
  if (a > b) swap(a, b);
  for (int l = 1, r; l <= a; l = r + 1) {
    
    r = min(a/(a/l), b/(b/l));
    ans += (mu[r] - mu[l - 1]) * (a/l) * (b/l);
  }
  return ans;
}

int main()
{
    
  init();
  int n, a, b, c, d, k;
  scanf("%d", &n);
  while (n--) {
    
    scanf("%d%d%d%d%d", &a, &b, &c, &d, &k);
    printf("%d\n", solve(b/k, d/k) - solve(b/k, (c - 1)/k) - solve((a - 1)/k, d/k) + solve((a - 1)/k, (c - 1)/k));
  }

  return 0;
}

GCD HDU - 1695

Problem Description

Given $5$ integers: $a,b,c,d,k,$ you’re to find $x$ in $a...b$, $y$ in $c...d$ that $gcd(x,y)=k$. $gcd(x,y)$ means the greatest common divisor of $x$ and $y$. Since the number of choices may be very large, you’re only required to output the total number of different number pairs.
Please notice that, ($x=5,y=7$) and ($x=7,y=5$) are considered to be the same.

You can assume that $a=c=1$ in all test cases.

Input

The input consists of several test cases. The first line of the input is the number of the cases. There are no more than $3,000$ cases.
Each case contains five integers: $a,b,c,d,k,0<a\le b\le 100,000,0<c\le d\le 100,000,0\le k\le 100,000$, as described above.

Output

For each test case, print the number of choices. Use the format in the example.

Sample Input

2
1 3 1 5 1
1 11014 1 14409 9

Sample Output

Case 1: 9
Case 2: 736427

Hint

For the first sample input, all the $9$ pairs of numbers are $(1,1),(1,2),(1,3),(1,4),(1,5),(2,3),(2,5),(3,4),(3,5)$.

题解

起始这题和上题差不多，一样的容斥。但是不同的是在这题看来，$(2,3)$ 和 $(3,2)$ 被看作是同样的一对，只计数一次。
题目已经说明保证 $a=c=1$。
所以我们只需要容斥进行这样子的处理：
令 $f=[gcd(x,y)=k]$ 。
$$num(f)=\sum _{x=1}^b\sum _{y=1}^{d}f-\frac{{\sum }_{x=1}^{min(b,d)}{\sum }_{y=1}^{min(b,d)}f}{2}$$
想想为什么？

因为只有满足 $x,y\in [1,min(b,d)]$ 才会有重复对的情况吧？

接下来对式子的处理也很容易。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 1e5 + 10;
int mu[maxn],prime[maxn], cnt = 0;
bool vis[maxn];

void init() {
    
  mu[1] = 1;
  for (int i = 2; i < maxn; i++) {
    
    if (vis[i] == false) {
    
      prime[cnt++] = i;
      mu[i] = -1;
    }
    for (int j = 0; j < cnt && prime[j] * i < maxn; j++) {
    
      vis[prime[j] * i] = true;
      if (i % prime[j] == 0) {
    
        mu[i * prime[j]] = 0;
        break;
      } else {
    
        mu[i * prime[j]] = -mu[i];
      }
    }
  }
  for (int i = 2; i < maxn; i++) {
    
    mu[i] += mu[i - 1];
  }
}

LL solve(int a, int b) {
    
  LL ans = 0;
  for (int l = 1, r; l <= a; l = r + 1) {
    
    r = min(a/(a/l), b/(b/l));
    ans += (LL)(mu[r] - mu[l - 1]) * (a/l) * (b/l);
  }
  return ans;
}

int main()
{
    
  init();
  int a, b, c, d, k, n;
  scanf("%d", &n);
  for (int ca = 0; ca < n; ca++) {
    
    scanf("%d %d %d %d %d", &a, &b, &c, &d, &k);
    if (k == 0) {
    
      printf("Case %d: 0\n", ca + 1);
      continue;
    }
    if (b > d) swap(b, d);
    printf("Case %d: %lld\n", ca + 1, solve(b/k, d/k) - solve(b/k, b/k)/2);
  }

  return 0;
}