题解 P2158 【[SDOI2008]仪仗队】

夏色祭 · 2017-12-29 20:29:00 · 题解

提高+的数论第一次过。。。(哭

经过一顿xjb骚推公式，我发现：

假设我们有两个点分别是(x1,y1)和(x2,y2)，那么只有当gcd(|x1-x2|,|y1-y2|)=1时，两个点才能互相看见。 那么这道题的答案也就是：gcd(x,y)=1的个数(0<=x<=n-1,0<=y<=n-1)

很容易就会想到欧拉函数。。。

一看数据范围只有4w，于是就没有码线性求欧拉函数我才不会告诉你们其实我并不不会，而是用了欧拉函数的通式：\phi(i)=i*\Pi(\frac{p-1}{p})（p是数i的质因数）

然后加了个lgn分解质因数，就nlgn的解决了问题。

代码：

#include<cstdio>
#define For(i,x,y) for (int i=x;i<=y;i++)
#define maxn 40010
using namespace std;
int p[maxn],m[maxn];
int n,tot,ans,x,y;
int gcd(int x,int y){
    if (y==0) return x;
        else return gcd(y,x%y);
}
void fj(int k){
    int last=0;
    while (m[k]!=k){
        if (m[k]!=last) x=x*(m[k]-1),y=y*m[k];
        last=m[k];
        k=k/m[k];
    }
    if (m[k]!=last) x=x*(m[k]-1),y=y*m[k];

}//用lgn分解质因数求出\Pi(\frac{p-1}{p})的分子和分母

int main(){
    scanf("%d",&n);
    For(i,2,n){
        if (!m[i]) p[++tot]=m[i]=i;
        for (int j=1;j<=tot&&i*p[j]<=n;j++){
            m[i*p[j]]=p[j];
            if (i%p[j]==0) break;
        }

}//欧拉筛

    For(i,0,n-1){
        if (i<=1){
            ans++;
            continue;
        }
        x=1,y=1;
        fj(i);
        int t=gcd(x,y);
        x=x/t,y=y/t;
        ans+=i/y*x;
    }
    printf("%d",ans*2-1);//注意最后答案要*2-1，首先gcd(x,y)=1的话gcd(y,x)=1所以就要*2，但是有个特例(1,1)就只能算一次
    return 0;
}