【poj 3090】Visible Lattice Points(数论--欧拉函数 找规律求前缀和)

题意:问从(0,0)到(x,y)(0≤x, yN)的线段没有与其他整数点相交的点数。

解法:只有 gcd(x,y)=1 时才满足条件,问 N 以前所有的合法点的和,就发现和上一题—— 【poj 2478】Farey Sequence(数论--欧拉函数 找规律求前缀和) 求 x/y,gcd(x,y)=1 且 x<y 很像。
   而由于这里 x可等于或大于y,于是就求 欧拉函数的前缀和*2+边缘2个点+对角线1个点。

 1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #include<iostream>
5 using namespace std;
6 #define N 1000
7 typedef long long LL;
8
9 int pr=0;
10 int prim[N+10],v[N+10],phi[N+10];
11 LL sphi[N+10];
12
13 void get_prime()
14 {
15 memset(v,0,sizeof(v));
16 for (int i=2;i<=N;i++)
17 {
18 if (!v[i]) prim[++pr]=i, phi[i]=i-1;
19 for (int j=1;j<=pr && i*prim[j]<=N;j++)
20 {
21 v[i*prim[j]]=1;
22 if (i%prim[j]!=0) phi[i*prim[j]]=phi[i]*phi[prim[j]];
23 else {phi[i*prim[j]]=phi[i]*prim[j]; break;}
24 }
25 }
26 sphi[1]=0;
27 for (int i=2;i<=N;i++) sphi[i]=sphi[i-1]+phi[i];
28 }
29 int main()
30 {
31 get_prime();
32 int T,n;
33 scanf("%d",&T);
34 for (int kase=1;kase<=T;kase++)
35 {
36 scanf("%d",&n);
37 printf("%d %d %lld\n",kase,n,2*sphi[n]+3);
38 }
39 return 0;
40 }
上一篇:Git常用操作汇总(转)


下一篇:C#之asp.net 及MVC 生成动态验证码: