[SDOI2008]仪仗队

P2158 [SDOI2008]仪仗队

题目描述

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

 

 现在,C君希望你告诉他队伍整齐时能看到的学生人数。

输入输出格式

输入格式:

共一个数N

输出格式:

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

输入输出样例

输入样例#1

4

输出样例#1

9

说明

【数据规模和约定】

对于 100% 的数据,1 ≤ N ≤ 40000

 

【题解】:

欧拉函数只对正整数有意义,对于phi(n),表示的是小于n的并且与n互质的正整数个数,通式:

phi(n)=n(1-1/p1)(1-1/p2)……(1-1/pm)

其中p1,p2,……,pm表示n的质因数(但不会重复出现,即p1!=p2!=……!=pm,比如phi(18)=18(1-1/2)(1-1/3))

这道题里面假设以观察者为原点,可以发现他能看到的人符合下面的两个特点:

1.要么是特殊值((1,0),(1,1),,(0,1)),要么横纵坐标互质

2.看到的人关于y=x对称

所以我们可以对2~n-1求欧拉函数,将所得值相加,就表示除了三个特殊点以外在y=x的某一侧上的可见点(具体原因建议你们意会一下画图)

然后假设得到的值是ans,则最终答案为ans*2+3

【AC代码】:

 

#include<iostream>
#include<cstdio>
using namespace std;
/*int phi(int n){//
    int k=2;
    double res=n; 
    for(;n>1;k++){
        if(n%k) continue;
        while(!(n%k)) n/=k;
        res*=(1.0-1.0/(double)k);
    }
    return res;
}*/
//BZOJ有毛病,上面的codevs,洛谷都过了,就是BZOJ.. 
//WA到挺phi换姿势 
int phi(int n){
    int ans=n;
    if(n&1^1){
        while(n&1^1) n>>=1;
        ans>>=1;
    } 
    for(int i=3;i*i<=n;i+=2){
        if(n%i==0){
            while(n%i==0) n/=i;
                ans=ans/i*(i-1);
        }
    }
    if(n>1) ans=ans/n*(n-1);
    return ans;
}
int main(){
    int n;scanf("%d",&n);
    int ans=0;
    for(int i=2;i<n;i++) ans+=phi(i);
    printf("%d",ans*2+3);
    return 0;
}

 --------------------------

源WA代码修改版(WA原因:1.0-1.0/(double)k有精度问题)

---------------------------

#include<iostream>
#include<cstdio>
using namespace std;
int phi(int p){
    int phi=p;
    for(int i=2;i*i<=p;i++){
        if(!(p%i)){
            phi=phi-phi/i;
            while(!(p%i)) p/=i;
        }
    }
    if(p>1) phi=phi-phi/p;
    return phi;
}
int main(){
    int n;scanf("%d",&n);
    if(n==1){puts("0");return 0;}
    int ans=0;
    for(int i=2;i<n;i++) ans+=phi(i);
    printf("%d",ans*2+3);
    return 0;
}