题目解析

题意分析

这道题目要求计算在第一象限中，从原点$(0,0)$到$(x,y)$（$0 \leq x,y \leq N$）的直线不经过任何其他格点的可见点的数量。具体规则如下：

1. 格点定义：

   • 点$(x,y)$，其中$x$和$y$为非负整数
   • 原点$(0,0)$不算作可见点

2. 可见性条件：

   • 点$(x,y)$可见当且仅当$\gcd(x,y)=1$
   • 即$x$和$y$互质

3. 特殊情况：

   • 坐标轴上的点$(x,0)$和$(0,y)$只有当$x=1$或$y=1$时才可见
   • 点$(1,1)$总是可见的

解题思路

1. 数学推导：

   • 可见点数量等于满足$1 \leq x,y \leq N$且$\gcd(x,y)=1$的点数加上坐标轴上的可见点
   • 可以使用欧拉函数$\phi(n)$计算与$n$互质的数的个数

2. 计算公式：

   • 总可见点数$V(N) = 3 + 2 \times \sum_{k=2}^N \phi(k)$
   • 其中：
     • $3$来自$(1,0)$、$(0,1)$和$(1,1)$
     • $2 \times \sum \phi(k)$计算第一象限内其他可见点（对称性）

3. 预处理优化：

   • 预先计算所有$N$的欧拉函数值
   • 使用筛法高效计算欧拉函数

//#pragma GCC optimize(2)
//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<queue>
// #include<unordered_map>
#define ll long long
#define inf 0x3f3f3f3f
#define Inf 0x3f3f3f3f3f3f3f3f
// #define int  ll
#define endl '\n'
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;
int read()
{
	int res = 0,flag = 1;
	char ch = getchar();
	while(ch<'0' || ch>'9')
	{
		if(ch == '-') flag = -1;
		ch = getchar();
	}
	while(ch>='0' && ch<='9')
	{
		res = (res<<3)+(res<<1)+(ch^48);//res*10+ch-'0';
		ch = getchar();
	}
	return res*flag;
}
const int maxn = 1e3+5;
const int mod = 1e9+7;
const double pi = acos(-1);
const double eps = 1e-8;
int n,m,cas,cnt,pri[maxn],mu[maxn],sum[maxn];
bool vis[maxn];
void get_mu() //筛莫比乌斯函数，求需要的函数的前缀和
{
	mu[1] = vis[1] = 1;
	for(int i = 2;i < maxn;i++)
	{
		if(!vis[i])
		{
			mu[i] = -1;
			pri[++cnt] = i;
		}
		for(int j = 1;j <= cnt && i*pri[j] < maxn;j++)
		{
			vis[i*pri[j]] = true;
			if(i%pri[j] != 0) mu[i*pri[j]] -= mu[i];
			else break;
		}
	}
	for(int i = 1;i < maxn;i++)
		sum[i] = sum[i-1]+mu[i];
}
int main()
{
	get_mu();
	int t = read();
	while(t--)
	{
		n = read();
		int res = 1;
		for(int l = 1,r;l <= n;l = r+1)
		{
			r = (n/(n/l));
			res += (sum[r]-sum[l-1])*(n/l)*(n/l);
		}
		printf("%d %d %d\n",++cas,n,1+res);
	}
	return 0;
}