紫书p339
枚举a，每个的贡献为b/i*phi[i]，因为gcd(kx+y,x)=gcd(x,y),因为gcd(x,y)=gcd(y,x%y)
#include <iostream> #include <cstdio> #include <ctime> #include <cstring> #include <algorithm> #include <vector> #include <map> #include <cmath> #include <set> #include <queue> using namespace std; typedef unsigned long long ll; const int INF=1e9+100; const int mod=1e9+7; int phi[2005]; void phi_table(int n){ memset(phi,0,sizeof(phi)); phi[1]=1; for(int i=2;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-1); } } } } ll gcd(ll x,ll y){ return y?gcd(y,x%y):x; } int main(){ //freopen("out.txt","w",stdout); int a,b; phi_table(2001); while(scanf("%d %d",&a,&b)&&a+b){ ll ans=0; for(int i=1;i<=a;i++){ int t=b/i; ans+=1LL*t*phi[i]; for(int j=t*i+1;j<=b;j++){ if(gcd(j,i)==1) ans++; } } ans=1LL*ans*4+4; double ans1=1.0*ans/((1LL*2*a+1)*(2*b+1)-1); printf("%.7f\n",ans1 ); } return 0; }