27 lines
733 B
C++
27 lines
733 B
C++
#include <bits/stdc++.h>
|
|
using namespace std;
|
|
const int N = 1010;
|
|
|
|
// 欧拉函数
|
|
int phi(int x) {
|
|
int res = x;
|
|
for (int i = 2; i * i <= x; i++) // 从2枚举到sqrt(x)
|
|
if (x % i == 0) { // 如果i是x的小因子
|
|
res = res / i * (i - 1);
|
|
while (x % i == 0) x /= i; //
|
|
}
|
|
if (x > 1) res = res / x * (x - 1);
|
|
return res;
|
|
}
|
|
|
|
int main() {
|
|
int n, m;
|
|
cin >> m;
|
|
for (int i = 1; i <= m; i++) {
|
|
cin >> n;
|
|
int res = 1; // x=y 记1个
|
|
for (int j = 1; j <= n; j++) res += phi(j) * 2; // 叠加两倍的欧拉函数值
|
|
printf("%d %d %d\n", i, n, res);
|
|
}
|
|
return 0;
|
|
} |