题意：

计算 $\sum_{k \in prime} \sum_{i=1}^{n} \sum_{j=1}^{m} \left [ gcd(i,j) = k \right ]$ 。

数据范围： $1 \leqslant n,m \leqslant 10^7$ 。

题解：

$\begin{aligned} ans&=\sum_{k\in prime}\sum_{i=1}^{n} \sum_{j=1}^{m} \left [ gcd(i,j) = k \right ] \\ &=\sum_{k\in prime} \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_{k\in prime}\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_{k\in prime}\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}$

算到这一步，需要换元降低时间复杂度。令 $T = kd$ 。

$ans = \sum_{T=1}^{n} \left \lfloor \frac{n}{T} \right \rfloor \left \lfloor \frac{m}{T} \right \rfloor \sum_{k\in prime , k \mid T} \mu(\frac{T}{k})$

$\sum_{k\in prime , k \mid T} \mu(\frac{T}{k})$ 可以 $O(nlogn)$ 筛出来，具体操作就是枚举素数的倍数。

这样就可以前缀和 + 整除分块求 $ans$ 了。

感受：

又被卡常，把能用int的地方全用int就好了。

学会了一种优化方法：自己筛一个东西。

代码：

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

上一篇：codeforces1236D 2100分模拟

下一篇：P2522 莫比乌斯反演

发表评论

关于作者

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

-- 愿君每日到此一游！

题意：

题解：

感受：

代码：

发表评论

最新留言

关于作者

推荐文章