本文共 1299 字，大约阅读时间需要 4 分钟。
P2158 [SDOI2008] 仪仗队
#include #include #include #include #include #include #include #include #include #include #define inf 2147483647#define For(i, a, b) for (register int i = a; i <= b; i++)#define p(a) putchar(a)#define g() getchar()// by war// 2017.11.3using namespace std;int n;int ans;int prime[40010];bool vis[40010];int cnt, tot;int pr[40010];void in(int &x) { int y = 1; char c = g(); x = 0; while (c < '0' || c > '9') { if (c == '-') y = -1; c = g(); } while (c >= '0' && c <= '9') x = (x < 1) ? (x < 3 ? x + 2 : x + c - '0') : x * 10 + c - '0'; x *= y;}void o(int x) { if (x < 0) { p('-'); x = -x; } if (x > 9) o(x / 10); p(x % 10 + '0');}void Euler() { For(i, 2, n) { if (!vis[i]) prime[++cnt] = i; for (register int j = 1; j <= cnt && i * prime[j] <= n; j++) { vis[i * prime[j]] = true; if (i % prime[j] == 0) break; } }}int Eulerfunction(int x) { tot = 0; int c = x; For(i, 1, cnt) { if (prime[i] > x) break; if (x % prime[i] == 0) pr[++tot] = prime[i]; } For(i, 1, tot) c -= c / pr[i]; return c;}int main() { in(n); n--; Euler(); For(i, 1, n) ans += Eulerfunction(i); o(ans * 2 + 1); return 0;}
转载于: https://www.cnblogs.com/war1111/p/7779707.html