洛谷 P2158 仪仗队

时间:2024-01-12 09:10:56

欧拉函数入门题...

当然如果有兴趣也可以用反演做...类似这题

题意就是求,方阵从左下角出发能看到多少个点。

从0开始给坐标

发现一个点能被看到,那么横纵坐标互质。

然后求欧拉函数的前缀和,* 2 + 1即可。

注意特判。

 #include <cstdio>
const int N = ; int p[N], phi[N], top;
bool vis[N]; inline void getphi(int b) {
phi[] = ;
for(int i = ; i <= b; i++) {
if(!vis[i]) {
p[++top] = i;
phi[i] = i - ;
}
for(int j = ; j <= top && i * p[j] <= b; j++) {
vis[i * p[j]] = ;
if(i % p[j] == ) {
phi[i * p[j]] = phi[i] * p[j];
break;
}
phi[i * p[j]] = phi[i] * (p[j] - );
}
}
return;
} int main() {
int n;
scanf("%d", &n);
if(n == ) {
printf("");
return ;
}
n--;
getphi(n);
int ans = ;
for(int i = ; i <= n; i++) {
ans += phi[i];
}
ans = ans * + ;
printf("%d", ans); return ;
}

AC代码

莫比乌斯反演:

求n以内gcd == 1的数对个数。

根据上面的方法搞一搞,最后 + 2即可。

也要特判。

 #include <cstdio>

 const int N = ;

 int p[N], miu[N], top;
bool vis[N]; inline void getmiu(int b) {
miu[] = ;
for(int i = ; i <= b; i++) {
if(!vis[i]) {
p[++top] = i;
miu[i] = -;
}
for(int j = ; j <= top && i * p[j] <= b; j++) {
vis[i * p[j]] = ;
if(i % p[j] == ) {
break;
}
miu[i * p[j]] = -miu[i];
}
}
return;
} int main() {
int n;
scanf("%d", &n);
n--;
if(!n) {
printf("");
return ;
}
getmiu(n); int ans = ;
for(int i = ; i <= n; i++) {
ans += miu[i] * (n / i) * (n / i);
}
printf("%d", ans + );
return ;
}

AC代码