CSU 1325 莫比乌斯反演

题目大意：

一、有多少个有序数对（x，y）满足1<=x<=A，1<=y<=B，并且gcd（x，y）为p的一个约数；

二、有多少个有序数对（x，y）满足1<=x<=A，1<=y<=B，并且gcd（x，y）为p的一个倍数。

第一行两个数：p和q。（1<p<10^7 ，1<q<1000。）

接下来有q行，每行两个数A和B。（1<A,B<10^7）

我们先考虑第二个问题，很简单答案就是 (A/p) * (B/p) , 因为从p开始每次叠加p枚举到A，B中间得到的数都是可以任意选择，gcd()的值必然是p的倍数的

我们考虑第一个问题，这里约数的个数不超过数字n的2sqrt(n)个

所以我们可以枚举出每一个约数k,然后对k进行求和

对于使用莫比乌斯反演求和的话只是从当前来说复杂度大概是

O(q*lg(p)*(sqrt(A)+sqrt(B)) //sqrt(A)是因为对莫比乌斯数组求前缀和进行快速计算，这是莫比乌斯中常出现的方式

为了较低复杂度，我们列式计算考虑降维

如下列公式所示：

$\sum_{k}\sum_{x=1}^{A}\sum_{y=1}^{B}[gcd(x,y)=k] = \sum_{k}\sum_{x=1}^{A/k}\sum_{y=1}^{B/k}[gcd(x,y)=1] = \sum_{k}\sum_{d}\mu (d)\sum_{x=1}^{A/k/d}\sum_{y=1}^{B/k/d}=\sum_{k}\sum_{d}\mu (d)\sum_{x=1}^{A/t}\sum_{y=1}^{B/t}[t=k*d] =\sum_{t}sum[t]\sum_{x=1}^{A/t}\sum_{y=1}^{B/t}$

最后是如何计算sum[t],能计算出sum[]数组的话，t最大不超过min(A,B)那么总复杂度就能降为O(q*(sqrt(A)+sqrt(B))就没问题了

这里t只跟k,d有关系，那么只要枚举每一个k,d就能得到sum[t]的数组了

for(int i=0 ; i<cnt ; i++){
        for(int d=1 ; d*fac[i]<=M ; d++){
            sum[d*fac[i]] += mu[d];
        }
    }
for(int i=1 ; i<=M ; i++) sum[i] += sum[i-1];

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 #include <cmath>
 5 
 6 using namespace std;
 7 #define ll long long
 8 #define N 10005
 9 #define M 10000000
10 int p,q,a,b,cnt;
11 int fac[N];
12 int mu[M+5] , prime[M/10] , tot , sum[M];
13 bool check[M+5];
14 
15 void get_mu()
16 {
17     mu[1] = 1;
18     for(int i=2 ; i<=M ; i++){
19         if(!check[i]){
20             mu[i] = -1;
21             prime[tot++] = i;
22         }
23         for(int j=0 ; j<tot ; j++){
24             if((ll)prime[j]*i>M) break;
25             check[prime[j]*i] = true;
26             if(i%prime[j]==0) break;
27             else mu[i*prime[j]] = -mu[i];
28         }
29     }
30 }
31 
32 void init()
33 {
34     int v = (int)sqrt(p+0.5);
35     for(int i=1 ; i<=v ; i++){
36         if(p%i==0){
37             fac[cnt++] = i;
38             if(p/i!=i) fac[cnt++] = p/i;
39         }
40     }
41 }
42 
43 void pre_solve()
44 {
45     for(int i=0 ; i<cnt ; i++){
46         for(int d=1 ; d*fac[i]<=M ; d++){
47             sum[d*fac[i]] += mu[d];
48         }
49     }
50     for(int i=1 ; i<=M ; i++) sum[i] += sum[i-1];
51 }
52 
53 ll cal(int a , int b)
54 {
55     ll ans = 0;
56     for(int t=1 , last ; t<=a ; t=last+1){
57         last = min(a/(a/t) , b/(b/t));
58         ans += (ll)(sum[last]-sum[t-1])*(a/t)*(b/t);
59     }
60     return ans;
61 }
62 
63 int main()
64 {
65     get_mu();
66     scanf("%d%d" , &p , &q);
67     init();
68     pre_solve();
69     while(q--){
70         scanf("%d%d" , &a , &b);
71         if(a>b) swap(a , b);
72         printf("%lld %lld\n" , cal(a,b) , (ll)(a/p)*(b/p));
73     }
74 }

CSU 1325 莫比乌斯反演

推荐阅读