洛谷 P2158 [SDOI2008]仪仗队 题解【数学】【gcd/lcm】【欧拉函数】【筛素数】

作者: wjyyy 分类: gcd/lcm,数学,欧拉函数,筛素数,解题报告 发布时间: 2018-07-02 21:15

点击量:26

 

 

   找规律??

题目描述

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

 

输入输出格式

输入格式:

共一个数N

 

输出格式:

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

 

输入输出样例

输入样例#1:
4
输出样例#1:
9

说明

【数据规模和约定】

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

 

   观察这个图,我们发现,在过原点的相同斜率的直线上只会有一个点被看到,那么我们如何把这种信息转化为方便的计算呢?如果我们把斜率用map存起来,不仅精度没有保证,还要验证40000×40000中每个点的合法性,时间上也不合适。

 

   但是可以看出,斜率相同,说明\(k=\frac{y_i}{x_i}\),我们如果把\(y_i\)和\(x_i\)约分,那么最终得出的结果一定是\(y_i\)与\(x_i\)互质。那么我们如果在第一次就把它统计出来,后面就不用统计了。因此我们有了思路:当某个点(x,y)有gcd(x,y)=1时,它就会被看到,此时可知x与y互质。

 

   互质可以用欧拉函数来求,其中\(\varphi(n)\)表示2~n中与n互质的数的个数,特殊地\(\varphi(1)=1\)。通过这个我们就可以求出n范围内互质的数的对数。

 

   再来观察图像,我们发现,图是对称的,那么答案就是\(2\times \sum\limits _{i=1}^{n}\varphi(i)\)。而当倾角为\(\frac \pi 4 \)时,只有1个,因此我们把它加上就行了。

 

   欧拉函数计算方法:\(\varphi(n)=n\times \prod\limits _{i=1}^{m}p_i\)(\(p_i\)是\(n\)的质因子,\(m\)是\(n\)的质因子个数),利用容斥原理可以证明。

 

    当n=1时看不到别人,所以输出0。

Code:

#include<cstring>
#include<cstdio>
#include<cmath>
bool in[40002];
int pri[10000],cnt=0;
long long euler(int x)
{
    long long ans=x;
    if(in[x])
        return x-1;
    for(int i=1;i<=cnt&&pri[i]<=x;i++)
        if(x%pri[i]==0)
        {
            ans*=pri[i]-1;
            ans/=pri[i];
        }
    return ans;
}
int main()
{
    memset(in,1,sizeof(in));
    int n;
    scanf("%d",&n);
    in[0]=false;
    in[1]=false;
    for(int i=2;i<=n;i++)
    {
        if(in[i])
            pri[++cnt]=i;
        for(int j=1;j<=cnt&&pri[j]*i<=n;j++)
        {
            in[pri[j]*i]=false;
            if(i%pri[j]==0)
                break;
        }
    }
    long long sum=0;
    for(int i=1;i<=n-1;i++)
        sum+=euler(i);
    sum*=2;
    sum+=(n!=1);//1的时候记得特判
    printf("%lld",sum);
    return 0;
}

 

说点什么

avatar
  Subscribe  
提醒
/* */