Trees in a Wood. UVA - 10214 欧拉函数表

紫书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;
}