欧拉函数入门题...
当然如果有兴趣也可以用反演做...类似这题
题意就是求，方阵从左下角出发能看到多少个点。
从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代码