Visible Lattice Points POJ - 3090

本文主要是介绍Visible Lattice Points POJ - 3090，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

http://poj.org/problem?id=3090

预处理答案 ans[i]比ans[i-1]多出来的部分 就是2*f(i) 也就是看多出来的一圈点中有多少点与(0,0)的横纵坐标之差互质 画画图就出来了

 

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn=1e3+10;int ans[maxn];int solve(int n)
{int i,res;res=n;for(i=2;i*i<=n;i++){if(n%i==0){res=res*(i-1)/i;while(n%i==0){n/=i;}}}if(n!=1){res=res*(n-1)/n;}return res;
}void init()
{int i,j;ans[1]=3;for(i=2;i<=1e3;i++){ans[i]=ans[i-1]+2*solve(i);}
}int main()
{int t,cas,n;init();scanf("%d",&t);for(cas=1;cas<=t;cas++){scanf("%d",&n);printf("%d %d %d\n",cas,n,ans[n]);}return 0;
}

 

这篇关于Visible Lattice Points POJ - 3090的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---