[luoguP2158] [SDOI2008]仪仗队（数论）

传送门

可以看出 (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; }

　　

上一篇：[luoguP1901] 发射站（单调栈）

下一篇：[luoguP1282] 多米诺骨牌（DP + 背包）

---

数论