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.
Sample Input
3 2 0 0
Sample Output
0.7058824
#include<bits/stdc++.h>
using namespace std;#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define read(x,y) scanf("%d%d",&x,&y)#define ll long long
#define root l,r,rt
#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
///算出3000内的欧拉函数值
/*
数学规律题，
注意到gcd(x,y)=1的点，
是可以直接看到的。对每一列进行计数，当然注意到题目中给的条件性质，
对b进行分块运算，然后简单数学处理下即可。详见代码
*/int gcd(int x,int y){return y==0?x:gcd(y,x%y);}const int maxn=4000;
ll phi[maxn];
void phi_table(int n)
{memset(phi,0,sizeof(phi));phi[1]=1;for(int i=2;i<=n;i++){if(phi[i]) continue;for(int j=i;j<=n;j+=i){if(!phi[j]) phi[j]=j;phi[j]=phi[j]/i*(i-1);}}
}ll get_phi(ll x)
{ll ans=x,ub=floor(sqrt(x+0.5));for(ll i=2;i<=ub;i++){if(x%i==0){ans=ans/i*(i-1);while(x%i==0) x/=i;}}if(x>1) ans=ans/x*(x-1);return ans;
}ll a,b;///坑点。。。输入时想的是ll,结果没注意类型标为了int。。。。int main()
{///phi_table(3000);while(scanf("%lld%lld",&a,&b)&&a){ll ans=0;for(ll i=1;i<=a;i++){ll k=b/i;ans+=k*get_phi(i);for(ll j=k*i+1;j<=b;j++) if(gcd(i,j)==1) ans++;}ans=ans*4+4;///cout<<ans<<endl;ll tot=(ll)(2*a+1)*(2*b+1)-1;printf("%.7f\n",1.0*ans/tot);}return 0;
}