【题目链接】
https://www.lydsy.com/JudgeOnline/problem.php?id=2190
【算法】
同POJ3090
值得注意的是此题数据规模较大，建议使用用线性筛筛出欧拉函数
【代码】
#include <algorithm> #include <bitset> #include <cctype> #include <cerrno> #include <clocale> #include <cmath> #include <complex> #include <cstdio> #include <cstdlib> #include <cstring> #include <ctime> #include <deque> #include <exception> #include <fstream> #include <functional> #include <limits> #include <list> #include <map> #include <iomanip> #include <ios> #include <iosfwd> #include <iostream> #include <istream> #include <ostream> #include <queue> #include <set> #include <sstream> #include <stdexcept> #include <streambuf> #include <string> #include <utility> #include <vector> #include <cwchar> #include <cwctype> #include <stack> #include <limits.h> using namespace std; #define MAXN 40010 int i,n,TC,T; int sum[MAXN]; inline void init() { int i,j,tmp,cnt = 0; static int f[MAXN],prime[MAXN],phi[MAXN]; for (i = 2; i < MAXN; i++) { if (!f[i]) { f[i] = prime[++cnt] = i; phi[i] = i - 1; } for (j = 1; j <= cnt; j++) { tmp = i * prime[j]; if (tmp >= MAXN) break; f[tmp] = prime[j]; if (prime[j] == f[i]) { phi[tmp] = phi[i] * prime[j]; break; } else phi[tmp] = phi[i] * (prime[j] - 1); } } for (i = 1; i < MAXN; i++) sum[i] = sum[i-1] + phi[i]; } int main() { init(); scanf("%d",&n); printf("%d ",2*sum[n-1]+3); return 0; }