BZOJ 2190: [SDOI2008]仪仗队

2190: [SDOI2008]仪仗队

Time Limit: 10 Sec  Memory Limit: 259 MB
Submit: 2689  Solved: 1713
[Submit][Status][Discuss]

Description

作为体育委员，C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵，为了保证队伍在行进中整齐划一，C君会跟在仪仗队的左后方，根据其视线所及的学生人数来判断队伍是否整齐(如下图)。 　　  　　现在，C君希望你告诉他队伍整齐时能看到的学生人数。

Input

共一个数N。

Output

共一个数，即C君应看到的学生人数。

Sample Input

　　4

Sample Output

　　9

HINT

【数据规模和约定】 　　对于 100% 的数据，1 ≤ N ≤ 40000

Source

分析：

问题可以转化为求Σ(1<=i<=n) Σ(1<=j<=n) [gcd(i,j)==1]

显然如果存在一个点(i*d,j*d)，那么它一定已经被(i,j)覆盖掉了...

根据Dirichlet卷积：e(i)=1 (if n=1)

0 (else)

e=μ×1，(f×g)(n)=Σ(d|n) f(d)*g(n/d)

我们可以把复杂度从n^2lgn化简为O(n)

Σ(1<=i<=n) Σ(1<=j<=n) [gcd(i,j)==1]

=Σ(1<=i<=n) Σ(1<=j<=n) e(gcd(i,j))

=Σ(1<=i<=n) Σ(1<=j<=n) Σ(d|gcd(i,j)) μ(d)

=Σ(1<=d<=n) μ(d)*(n/d)*(n/d)

代码：

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
//by NeighThorn
using namespace std;
//大鹏一日同风起，扶摇直上九万里

const int maxn=40000+5;

int n,ans,cnt,miu[maxn],prime[maxn],vis[maxn];

signed main(void){
    ans=cnt=0;
    scanf("%d",&n);miu[1]=1;n--; 
    memset(vis,0,sizeof(vis));
    for(int i=2;i<=n;i++){
        if(!vis[i])
            prime[++cnt]=i,miu[i]=-1;
        for(int j=1;j<=cnt&&prime[j]*i<=n;j++){
            vis[i*prime[j]]=1,miu[i*prime[j]]=-miu[i];
            if(i%prime[j]==0){
                miu[i*prime[j]]=0;break;
            }
        }
    }
    for(int i=1;i<=n;i++)
        ans+=miu[i]*(n/i)*(n/i);
    printf("%d\n",ans+2);
    return 0;
}

---

by NeighThorn