快速求1~n这n个数的欧拉函数的应用。。。
开始一直TLE。。最后过是因为跑欧拉函数那个函数提前跑一次，如果放在while里就TLE了。。
//============================================================================// Name : 2478.cpp// Author : // Version :// Copyright : Your copyright notice// Description : Hello World in C++, Ansi-style//============================================================================#include#include #include using namespace std;int n;int a[1000010];long long ans;void euler(){ for(int i = 1;i <= 1000000;i++){ a[i] = 0; } a[1] = 1; for(int i = 2;i <= 1000000;i++){ if(!a[i]){ for(int j = i;j <= 1000000;j += i){ if(!a[j]){ a[j] = j; } a[j] = a[j]/i*(i-1); } } } return ;}int main() { freopen("a.txt", "r", stdin); euler(); while(scanf("%d", &n)&&n){ ans = 0; for(int i = 2;i <= n;i++){ ans += a[i]; } printf("%I64d\n", ans); } return 0;}