AcWing 201. 可见的点
原题链接
简单
作者:
清风qwq
,
2022-07-04 09:53:27
,
所有人可见
,
阅读 332
#include <bits/stdc++.h>
using namespace std;
const int N = 1010;
int q[N], g[N], tot;
bool p[N];
void init()
{
g[1] = 1;
for (int i = 2; i < N; i ++ )
{
if (!p[i])
{
q[++tot] = i;
g[i] = i - 1;
}
for (int j = 1; q[j] <= N / i; j ++ )
{
p[i * q[j]] = true;
if (i % q[j] == 0)
{
g[i * q[j]] = g[i] * q[j];
break;
}
g[i * q[j]] = g[i] * (q[j] - 1);
}
}
}
int main()
{
init();
int T, Case = 1;
cin >> T;
while (Case <= T)
{
int n, res = 0;
cin >> n;
for (int i = 1; i <= n; i ++ )
res += g[i];
printf("%d %d %d\n", Case++, n, 2 * res + 1);
}
return 0;
}
orz