首页 > 代码库 > ACdream 1148 GCD SUM (久违的莫比乌斯)

ACdream 1148 GCD SUM (久违的莫比乌斯)

题目链接

题意:给出N,M
执行如下程序:
long long  ans = 0,ansx = 0,ansy = 0;
for(int i = 1; i <= N; i ++)
   for(int j = 1; j <= M; j ++)
       if(gcd(i,j) == 1) ans ++,ansx += i,ansy += j;
cout << ans << " " << ansx << " " << ansy << endl;


思路: 首先要会莫比乌斯,然后对于ans,自然是非常好求的,现在就是怎么求ansx和ansy。 设



反演后得到:



因为n/i,m/i的值是分段的,每段都是相同的,分别有sqrt级别的段数,所以(n/i, m/i)也是sqrt级别的段数。所以这个可以分段求了,然后预处理出i*mu(i)的前缀和即可!


code:

<script src="https://code.csdn.net/snippets/442010.js" type="text/javascript"></script>