传送门
可以看出 (i, j) 能被看到，(i * k, j * k) 都会被挡住
暴力
所以 gcd(i, j) == 1 的话 ans ++
那么可以枚举一半(中轴对称)，求解答案，只能拿30分
#include <cstdio> #include <iostream> int n, ans; inline int read() inline int gcd(int x, int y) int main() for(i = 1; i < n; i++) for(j = i + 1; j < n; j++) if(gcd(i, j) == 1) ans++; printf("%d\n", ans * 2 + 3); return 0; }正解
可以看出，gcd(i,j) == 1 才能对答案有贡献，也就是互质，想到什么？phi 值
其实上面的暴力过程仔细来看也就是 phi 值 的求解
#include <cstdio> #include <iostream> int n, ans; int phi[500001]; inline int read() inline void euler_phi() } int main() euler_phi(); for(i = 1; i < n; i++) ans += phi[i]; printf("%d\n", ans * 2 + 1); return 0; }
上一篇：[luoguP3146] [USACO16OPEN]248（区间DP）
下一篇：[luoguP1280] 尼克的任务（DP）
数论
