题解 P2158 【[SDOI2008]仪仗队】

· · 题解

思路

这道题的具体做法楼上dalao已经讲的非常清楚了qwq

具体地，我们沿着对角线将这个正方形切开，得到两个直角三角形。

我们发现，实际上要求的答案大概就是在1到n的范围里不同的gcd（i，j）的个数，对于一个特定的i，gcd（i，j）的个数就是i-1的欧拉函数值。

那么我们就将这个问题转化成为了欧拉函数的版子题。

代码实现

我们使用筛法求euler函数，一次性计算完毕，能在0ms内跑完所有的测试点。

#include <bits/stdc++.h>
using namespace std;
int n,euler[400001];
void Euler(int Max){
    Max=n-1;
    euler[1]=1;    
    for(int i=2;i<=Max;i++)    
    euler[i]=i;    
    for(int i=2;i<=Max;i++)    
    if(euler[i]==i)    
    for(int j=i;j<=Max;j+=i)    
    euler[j]=euler[j]/i*(i-1);
}//上面是线性欧拉函数的版子
int main() {
    scanf("%d",&n);
    Euler(n);
    int ans=0;
    for (int i=1;i<=n-1;i++)
    ans+=euler[i];
    printf("%d",ans*2+1);//最后我们将答案×2，因为我们只计算了一个直角三角形，同时加上1，因为对角线方向依然能看到一个同学
    return 0;
}