【題解】Luogu P2158 【[SDOI2008]仪仗队】

第一次居然写了个大暴力(Point类和gcd判断),[O(n^2 * (logN)^N)]吧,不过可以用来对拍嘻嘻

发现居然没有莫比乌斯的代码(楼下应该有大佬提过这个解法,但是好像没给代码)

在经过大佬的一番提示后,终于发现此题最xxx方法是:莫比乌斯反演

题意简化之后就是求gcd(i,j) = 1的个数

其实我觉得这都可以算作莫比乌斯反演的一大应用(求的个数)的模板了。而且不需要用类似分块的公共乘积优化。(这是玄学)

具体的推导过程可见https://www.luogu.org/blog/Cinema/mobius-inversion-formula

在这里我就只给结论了

设f(k)为gcd(i,j) = k的个数,由反演可得


μ(x)为莫比乌斯函数,具体可看上面的链接

于是我们可以用线筛预处理μ(x)
然后开始咱的反演
时间复杂度O(n + n) [= O(n)吧];

代码如下:

#include<cstdio>
#include<algorithm>

using namespace std;

const int L = 66666;
int mu[L] = {},primes[L] = {};
bool isPrime[L] = {};
int n,num;

//线筛预处理莫比乌斯函数
void sieve(){
    fill(isPrime,isPrime + L,true);

    mu[1] = 1;
    num = 0;

    for(int i = 2;i < L;++i){
        if(isPrime[i]){
            primes[num++] = i;
            mu[i] = -1;
        }
        static int d;
        for(int j = 0;j < num && (d = i * primes[j]) < L;++j){
            isPrime[d] = false;
            if(i % primes[j] == 0){
                mu[d] = 0;
                break;
            }else{
                mu[d] = -mu[i];
            }
        }
    }
}

int f(int n,int k){
    int ans = 2;

    if(n == 1){
        return 0;
    }

    for(int x = 1;x < n;x++){
        ans += mu[x] * ((n - 1) / (k * x)) * ((n -1) / (k * x));
    }

    return ans;
}

int main(){
    scanf("%d",&n);

    sieve();//记得调用

    printf("%d",f(n,1));

    return 0;
}

发布者:Cinema

成功的道路并不狭窄,因为大部分人都在颓废。

加入对话

1条评论

电子邮件地址不会被公开。 必填项已用*标注