紫书例题 10-27 UVa 10214（欧拉函数）

只看一个象限简化问题，最后答案乘4+4

象限里面枚举x，在当前这条固定的平行于y轴的直线中

分成长度为x的一段段。符合题目要求的点gcd（x，y） = 1

那么第一段1<= y <= x，个数为phi（x）个，即是x的欧拉函数值

第二段x+1 <= y <= 2x，因为gcd(x + i, x) = gcd(x, i)

接下来同理

一直到最后一段

kx + 1 <= y <= b要单独一个个算，因为最后一段的长度不一定为x

感觉这道题算每一条直线时分成长度为x的一段段很巧妙，不好想到

#include<cstdio>

#include<cmath>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

using namespace std;

typedef long long ll;

int phi(int n)

{

	int ans = n;

	for(int i = 2; i * i <= n; i++)

		if(n % i == 0)

		{

			ans = ans / i * (i - 1);

			while(n % i == 0) n /= i;

		}

	if(n > 1) ans = ans / n * (n - 1);

	return ans;

}

int gcd(int a, int b) { return !b ? a : gcd(b, a % b); }

ll f(int a, int b)

{

	ll ans = 0;

	REP(x, 1, a + 1)

	{

		int k = b / x;

		ans += phi(x) * k;

		REP(y, k*x + 1, b + 1)

			if(gcd(x, y) == 1)

				ans++;

	}

	return 4 * ans + 4;

}

int main()

{

	int a, b;

	while(~scanf("%d%d", &a, &b) && a)

	{

		ll K = f(a, b);

		ll N = (ll)(2 * a + 1) * (2 * b + 1) - 1;

		printf("%.7lf\n", (double)K / N);

	}

	return 0;

}

巴特西

紫书例题 10-27 UVa 10214（欧拉函数）

最新文章

热门文章

巴特西

紫书 例题 10-27 UVa 10214（欧拉函数）

最新文章

热门文章

紫书例题 10-27 UVa 10214（欧拉函数）