题目描述
作为体育委员,C君负责这次运动会仪仗队的训练。仪仗队是由学生组成的N * N的方阵,为了保证队伍在行进中整齐划一,C君会跟在仪仗队的左后方,根据其视线所及的学生人数来判断队伍是否整齐(如下图)。 现在,C君希望你告诉他队伍整齐时能看到的学生人数。
输入输出格式
输入格式:
共一个数N
输出格式:
共一个数,即C君应看到的学生人数。
输入输出样例
输入样例#1:
4
输出样例#1:
9
说明
【数据规模和约定】
对于 100% 的数据,1 ≤ N ≤ 40000
不难发现
以C君为(0,0)点构成坐标系
只有该店的横坐标与纵坐标互质时才能被看到
那么就变成就欧拉函数问题
单个求欧拉版
#include<cstdio>
using namespace std;
const int maxn = ;
int oula[maxn];
int prime[maxn];
bool a[maxn];
int n;
int phi(int x)
{
int ret=;
for(int i=;i*i<=x;i++)
{
if(x%i==)
{
ret*=i-,x/=i;
while(x%i==)
{
ret*=i;x/=i;
}
}
}
if(x>)ret*=x-;
return ret;
} int main ()
{
scanf("%d",&n);
int ans=;
for(int i=;i<n;i++)
{
ans+=phi(i);
}
ans=ans*,ans+=;
printf("%d\n",ans);
return ;
}
一起求版
#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int n;
const int maxn =;
int phi[maxn];
void get_phi() {
phi[]=;
for(int i=; i<=n; i++) {
if(!phi[i])
for(int j=i; j<=n; j+=i) {
if(!phi[j])phi[j]=j;
phi[j]=phi[j]/i*(i-);
}
}
}
int main() {
scanf("%d",&n);
get_phi();
int ans=;
for(int i=; i<=n-; i++)ans+=phi[i];
printf("%d",*ans+);
return ;
}