uva10214 Trees in a Wood.

2023-11-07 20:58

文章标签 trees wood uva10214

本文主要是介绍uva10214 Trees in a Wood.，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

The saying “You can’t see the wood for the trees” is not only a
cliche, but is also incorrect. The real problem is that you can’t see
the trees for the wood. If you stand in the middle of a wood, the
trees tend to obscure each other and the number of distinct trees you
can actually see is quite small. This is especially true if the trees
are planted in rows and columns, because they tend to line up. The
purpose of this problem is to ﬁnd how many distinct trees one can see
if one were standing on the position of a tree in the middle of the
wood. For a mathematically more precise description we assume that you
are situated at the origin of a coordinate system in the plane. Trees
are planted at all positions (x,y) ∈ ZZ×ZZ{(0,0)}, with |x|≤ a and
|y|≤ b. A tree at position (x,y) can be seen from the origin if there
are no other trees on the straight line from (0,0) to (x,y). Find the
number K of all the trees in the wood that can be seen from the origin
and the number N of all the trees to compute the fraction K N . Hint:
The Euler phi function φ(n) is deﬁned to be the number of integers m
in the range 1 ≤ m ≤ n relatively prime to n: φ(n) = #{m | 1 ≤ m ≤ n
and gcd(m,n) = 1} (gcd = greatest common divisor) Instead of counting
(an adequate method for small n!) you could as well use the following
identity: φ(n) = n ∏ p∈P,p|n(1− 1 p), P = {p ∈ IN|p prime} Hint:
Remember that gcd(m,n) = gcd(m + n,n) = gcd(m + 2n,n) = gcd(m + in,i)
You might be surprised that the fraction K N converges to 6 π2 ≈
0.607927 for an inﬁnitely largewood. Input Each scenario consists of a line with the two numbers a and b (separated by a white space), with 1
≤ a ≤ 2000 and 1 ≤ b ≤ 2000000. Input is terminated by a line with two
zeros. Output For each scenario print a line containing the fraction
with a precision of 7 digits after the decimal point. Error less than
2e-7 or 2∗10−7 will be tolerated.

求出所有互质的数对(x,y)(1<=x<=a,1<=y<=b)的个数ans，那么答案就是(4 * ans+4)/((2 * a+1) * (2 * b+1)-1)。
因为a比较小，b比较大，所以枚举i=1..a，计算1..b中与i互质的数。
不难发现，在区间[1..i],[i+1..2*i],…中各有phi(i)个满足条件的数，最后一段长度不正好为i的O(i)暴力即可。

#include<cstdio>
#include<cstring>
#define LL long long
int phi[2010],gcd[2010][2010];
int find(int a,int b)
{if (b==0) return a;if (gcd[a][b]) return gcd[a][b];return gcd[a][b]=find(b,a%b);
}
int main()
{int i,j,k,p,q,a,b;LL x,y,z,ans;phi[1]=1;for (i=2;i<=2000;i++)if (!phi[i])for (j=i;j<=2000;j+=i){if (!phi[j]) phi[j]=j;phi[j]=phi[j]/i*(i-1);}for (i=1;i<=2000;i++)for (j=1;j<=2000;j++)gcd[i][j]=find(i,j);while (scanf("%d%d",&a,&b)&&a){ans=0;for (i=1;i<=a;i++){ans+=(LL)phi[i]*(b/i);for (j=1;j<=b%i;j++)if (gcd[i][j]==1)ans++;}printf("%.7f\n",((double)ans*4+4)/((2*(double)a+1)*(2*b+1)-1));}
}