POJ 3090 坐标系上的视线遮蔽问题
Description
A lattice point (x, y) in the first quadrant (x and y are integers greater than or equal to 0), other than the origin, is visible from the origin if the line from (0, 0) to (x, y) does not pass through any other lattice point. For example, the point (4, 2) is not visible since the line from the origin passes through (2, 1). The figure below shows the points (x, y) with 0 ≤ x, y ≤ 5 with lines from the origin to the visible points.
Write a program which, given a value for the size, N, computes the number of visible points (x, y) with 0 ≤ x, y ≤ N.
Input
The first line of input contains a single integer C (1 ≤ C ≤ 1000) which is the number of datasets that follow.
Each dataset consists of a single line of input containing a single integer N (1 ≤ N ≤ 1000), which is the size.
Output
For each dataset, there is to be one line of output consisting of: the dataset number starting at 1, a single space, the size, a single space and the number of visible points for that size.
Sample Input
4
2
4
5
231
Sample Output
1 2 5
2 4 13
3 5 21
4 231 32549 这题目求的是视线所及未挡住的点
因为如(4,2)这样的点,gcd(4,2)=2!=1,有(2,1)将其挡住了。所以这题变向再求下x,y互质的点
可以从斜对角线对半分开,算一半最后乘2即可 代码如下:
#include <iostream>
#include <stdio.h>
#include <cstring>
using namespace std;
#define LL long long
#define N 1010
int phi[];
int F[]; void get_phi()
{
memset(phi,,sizeof(phi));
phi[]=;
for(int i=;i<=N;i++)
{
if(!phi[i])
for(int j=i;j<=N;j+=i)
{
if(!phi[j]) phi[j]=j;
phi[j]=phi[j]*(i-)/i;
}
}
} int main()
{
F[]=;
get_phi();
for(int i=;i<=N;i++) F[i]=F[i-]+phi[i];
int n,T;
cin>>T;
for(int i=;i<=T;i++){
cin>>n;
cout<<i<<' '<<n<<' '<<F[n]*+<<endl;
}
return ;
}
最新文章
- CentOS7安装NodeJS6.9
- 清除浮动clear/BFC
- 基于DDD的.NET开发框架 - ABP缓存Caching实现
- 安装m2crypto报错swig error : Unrecognized option -builtin
- BestCoder27 1002.Taking Bus(hdu 5163) 解题报告
- 【iM_VGA模块】运行 ucgui 演示!
- 转:linux的源码查看, c++语法 查看网站
- bootloader启动代码init.s解析----IRQ中断处理函数
- htm的常见布局
- Android的SharedPreferences(首选项)保存键值对
- Memcache 运行情况
- Nginx CONTENT阶段 concat模块
- [转载] HBase入门
- solr7.7.0搜索引擎使用(四)(搜索语法)
- html 之 padding,margin
- php字符串 统计个数
- 带包的java类在cmd环境下的执行办法
- #error和line
- 【Python入门总结】
- hadoop之mapreduce编程实例(系统日志初步清洗过滤处理)