搜索
您的当前位置:首页正文

Trees in a Wood.

来源:易榕旅网

#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
using namespace std;

const int MAXN = 2000;

int phi[MAXN + 1];

void InitPhi() {
	phi[1] = 1;
	for (int i = 2; i <= MAXN; ++i) {
		if (!phi[i]) {
			for (int j = i; j <= MAXN; j += i) {
				if (!phi[j]) {
					phi[j] = j;
				}
				phi[j] = phi[j] / i * (i - 1);
			}
		}
	}
}

//gcd(a,b)=gcd(b,a%b)
//gcd(a,0)=a
int gcd(int a, int b) {
	while (b) {
		int temp = a % b;
		a = b;
		b = temp;
	}
	return a;
}

int main(){
	InitPhi();
	int a, b;
	while (cin >> a >> b && a && b) {
		long long K = 0;
		for (int raw = 1; raw <= a; ++raw) {
			const long long k = b / raw;
			K += k * phi[raw];
			for (int y = k * raw + 1; y <= b; ++y) {
				if (gcd(y, raw) == 1) {
					++K;
				}
			}
		}

		const long long N = static_cast<long long>(2 * a + 1) * static_cast<long long>(2 * b + 1) - 1ll;
		K *= 4;
		K += 4;
		printf("%.7lf\n", static_cast<double>(K) / static_cast<double>(N));
	}
	return 0;

}

因篇幅问题不能全部显示,请点此查看更多更全内容

Top