题意：

计算 $\dpi{150} \sum_{i=a}^{b} \sum_{j=c}^{d} \left [ gcd(i,j) = k \right ]$ 。

数据范围： $1 \leqslant n,k \leqslant 5\cdot 10^4$ ， $1 \leqslant a \leqslant b \leqslant 5\cdot 10^4$ ， $1 \leqslant c \leqslant d \leqslant 5\cdot 10^4$ 。

题解：

首先可以化成二维前缀和解决这个问题。

设 $f(n,m) = \sum_{i=1}^{n} \sum_{j=1}^{m} \left [ gcd(i,j) = k \right ]$ 。

那么 $\sum_{i=a}^{b} \sum_{j=c}^{d} \left [ gcd(i,j) = k \right ] = f(b,d)-f(a-1,d)-f(b,c-1)+f(a-1,c-1)$ 。

只要会求 $f(n,m)$ 就解决这个问题了。

$\begin{aligned} f(n,m) &= \sum_{i=1}^{n} \sum_{j=1}^{m} \left [ gcd(i,j) = k \right ] \\ &= \sum_{i=1}^{\left \lfloor \frac{n}{k} \right \rfloor} \sum_{j=1}^{\left \lfloor \frac{m}{k} \right \rfloor} \left [ gcd(i,j) = 1 \right ] \\ &= \sum_{i=1}^{\left \lfloor \frac{n}{k} \right \rfloor} \sum_{j=1}^{\left \lfloor \frac{m}{k} \right \rfloor} \sum_{d \mid gcd(i,j)} \mu(d) \\ &= \sum_{d=1}^{\left \lfloor \frac{n}{k} \right \rfloor} \mu(d) \left \lfloor \frac{n}{kd} \right \rfloor \left \lfloor \frac{m}{kd} \right \rfloor \end{aligned}$

这里用到了莫比乌斯函数的性质： $\left [ n = 1 \right ] = \sum_{d \mid n} \mu(d)$ 。把 $n$ 换成 $gcd(i,j)$ 就行了。

感受：

int比long long快很多，最大的答案也不会爆int。

初学莫比乌斯，感觉一点也不简单，不过做了之后发现就是套路。

代码：

#include
   
    using namespace std ;typedef long long ll ;const int maxn = 5e4 + 5 ;int a , b , c , d , k ; bool vis[maxn] ;int prime[maxn] ;int mu[maxn] , pre_mu[maxn] ;int cnt = 0 ;void get_mu(int n){   pre_mu[1] = 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 && prime[j] * i <= n ; j ++)     {       vis[prime[j] * i] = 1 ;       if(i % prime[j] == 0)  break ;        else  mu[i * prime[j]] = -mu[i] ;     }     pre_mu[i] = pre_mu[i - 1] + mu[i] ;   }}int cal(int n , int m){   int ans = 0 ;   for(int l = 1 , r ; l <= n ; l = r + 1)   {     r = min(n / (n / l) , m / (m / l)) ;     ans += (pre_mu[r] - pre_mu[l - 1]) * (n / l) * (m / l) ;   }   return ans ;}int solve(int n , int m){	if(n <= 0 || m <= 0)  return 0 ;	if(n > m)  swap(n , m) ;	return  cal(n / k , m / k) ;}int main(){	int t ;	int n = 5e4 ;	scanf("%d" , &t) ;	get_mu(n) ;	while(t --)	{		scanf("%d%d%d%d%d" , &a , &b , &c , &d , &k) ;		int ans = solve(b , d) - solve(a - 1 , d) - solve(b , c - 1) + solve(a - 1 , c - 1) ;		printf("%d\n" , ans) ;	}	return 0 ;}

上一篇：P2257 莫比乌斯反演

下一篇：codeforces1304F2 dp + 单调队列优化

发表评论

关于作者

喝酒易醉，品茶养心，人生如梦，品茶悟道，何以解忧？唯有杜康！

-- 愿君每日到此一游！

题意：

题解：

感受：

代码：

发表评论

最新留言

关于作者

推荐文章