类似 https://www.cnblogs.com/towboa/p/17303216.html ,
不过给的是n ,m (n<=2000)
枚举 i (1<=i<=n) ,考虑 有多少 j (1<=j<=m) gcd__(i,j)==0
然后分段考虑
(gcd(x,y) = gcd(x,y-x) )
#include <iostream> #include <cstring> #include <cmath> #include <algorithm> using namespace std ; const int N =3e5+4; const int M=1e6; int vis[M+4],P[M+4],cnt; int fi[M+4]; int sum[N] ; int gcd(int x,int y){ return y==0?x: gcd(y,x%y); } void shai(int top){ cnt=0; fi[1]=1; for(int i=2;i<=top;i++){ if(vis[i]==0){ P[++cnt]=i; fi[i]=i-1; } for(int j=1;j<=cnt&&i*P[j]<=top;j++){ vis[i*P[j]]=1; if(i%P[j]==0){ fi[i*P[j]]=fi[i]*P[j]; break; } else fi[i*P[j]]=fi[i]*(P[j]-1); } } } signed main(){ int x,y; shai(2002); int a,b; long long ans; while(scanf("%d%d",&a,&b)!=EOF){ if(!a) return 0; ans=0; ans+=b+1; for(int i=2;i<=a;i++) { ans+=1ll*b/i*fi[i]; for(int j=b/i*i+1;j<=b;j++) ans+=__gcd(i,j)==1; } ans<<=2; printf("%.7lf\n",1.0*ans/(1ll*a*b*4+2*(a+b))); } }