UVA10375
显然,题目要求有多少二元组$(x,y)$满足$1\leq x,y\leq n且x,y互素$。
根据欧拉函数$\phi$的定义,$\phi (n)$为小于n且与n互素的整数个数。
定义$f(n)=\sum\limits_{i=2}^{n}\phi(i)$
那么对于$x< y或x>y$,都有$f(n)$个整数对满足条件,再加上$(1,1)$,答案为$2*f(n)+1$。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46
| #include <iostream> #include <algorithm> #include <cmath> #include <vector> using namespace std;
const int MAXN = 50001;
int phi[MAXN + 1]; int sum[MAXN + 1];
void Initphi() { phi[1] = 1; for (int i = 2; i <= MAXN; ++i) { if (!phi[i]) { for (int j = i; j <= MAXN; j += i) { if (!phi[j]) { phi[j] = j; } phi[j] = phi[j] / i * (i - 1); } } } return; }
void InitSum() { sum[2] = phi[2]; for (int i = 3; i <= MAXN; ++i) { sum[i] += sum[i - 1] + phi[i]; } }
int main(){ Initphi(); InitSum(); int n; while (cin >> n && n) { printf("%d\n", 2 * sum[n] + 1); } return 0;
}
|