思考:
前面的点会挡住后面的点,而后面的点的x和y坐标都是前面点x和y的倍数。
所以如果两个点是不是互质的,则会被(x/公约数,y/公约数)
给挡住。
所以可见点都是互质的。
实现1:直接__gcd, $O(n^2logn)$:
所以我们可以__gcd(x,y)
判断每个点的两坐标元素是否是互质,如果是,赋值为1。
多次询问,二维前缀和维护。
Code:
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 2010;
int T, n, m, a[N][N];
void pre()
{
for(int i=1;i<=1000;i++){ //如果是互质,赋值为1
for(int j=1;j<=1000;j++){
if(__gcd(i,j)==1) a[i][j]=1;
}
}
for(int i=1;i<=1000;i++) //维护二维前缀和
for(int j=1;j<=1000;j++){
a[i][j]+=a[i-1][j]+a[i][j-1]-a[i-1][j-1];
}
}
int main(){
pre();
cin>>T;
for(int i=1;i<=T;i++)
{
cin>>n;
cout<<i<<" "<<n<<" "<<a[n][n]+2<<'\n'; //加上(1,0),(0,1)两个点
}
return 0;
}
实现2:欧拉函数,$O(n)$:
主对角线将整个矩形分开,上下对称,所以只要计算出下面的答案*2即可。
分开后,对于第j列,行i的范围为 (0 ~ i-1)。需要判断这些行中,有多少 i 是和 j 互质的。
就是求出每一列的欧拉函数。
对于边长为n的方阵,答案为 $2*(φ(1) + φ(2) + φ(3) + … + φ(n) ) + 1$。
多次询问,前缀和维护。
Code:
#include <algorithm>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 2010;
int T, n, m, a[N][N];
int phi[N],s[N],prim[N],cnt;
bool f[N];
void euler() //线性筛法求欧拉函数
{
n=1000;
phi[1]=1;
for(int i=2;i<=n;i++)
{
if(!f[i]) prim[++cnt]=i,phi[i]=i-1;
for(int j=1;prim[j]<=n/i;j++)
{
f[prim[j]*i]=1;
if(i%prim[j]==0){
phi[prim[j]*i]=prim[j]*phi[i];
break;
}
phi[prim[j]*i]=(prim[j]-1)*phi[i];
}
}
}
int main(){
euler(); //求每一列的欧拉函数
for(int i=1;i<=1000;i++) s[i]=phi[i]+s[i-1]; //前缀和维护
cin>>T;
for(int i=1;i<=T;i++)
{
cin>>n;
cout<<i<<" "<<n<<" "<<2*s[n]+1<<"\n";
}
return 0;
}
终于找到一个第一个想法和我一样的了
大佬代码真清晰
yes
yes