制作公司网页可以用网上图片吗,关键词排名手机优化软件,房屋装修设计app,织梦网站栏目不显示题目链接 题目大意#xff1a; 给出范围为(0, 0)到(n, n)的整点#xff0c;你站在(0,0)处#xff0c;问能够看见几个点。 解题分析#xff1a;很明显#xff0c;因为 N (1 ≤ N ≤ 1000) #xff0c;所以无论 N 为多大#xff0c;(0,1),(1,1),(1,0)这三个点一定…题目链接 题目大意 给出范围为(0, 0)到(n, n)的整点你站在(0,0)处问能够看见几个点。 解题分析很明显因为 N (1 ≤ N ≤ 1000) 所以无论 N 为多大(0,1),(1,1),(1,0)这三个点一定能够看到除这三个点以外我们根据图像分析可得设一个点的坐标为(x,y) 那么只有符合gcd(x,y)1的点才能被看到。又因为 (0,0)---(n,n)对角线两端的点对称所以我们只需算一边即可而一边的点数根据欧拉函数可得 $\sum_{i2}^{n}\varphi{(i)}$ 所以最终的点数为$$2*\sum_{i2}^{n}\varphi{(i)}3$$ #include cstdio
#define N int(1e310)
typedef long long ll;
int euler[N];
void init(){euler[1]1;for(int i2;iN;i)euler[i]i;for(int i2;iN;i)if(euler[i]i)for(int ji;jN;ji)euler[j]euler[j]/i*(i-1);
}
int main(){init();int T,ncase0;scanf(%d,T);while(T--){int n;scanf(%d,n);ll ans0;for(int i2;in;i)anseuler[i];printf(%d %d %d\n,ncase,n,2*ans3);}
} 2019-02-12转载于:https://www.cnblogs.com/00isok/p/10363755.html
