pe562.c

typedef long long int64;
typedef unsigned long long uint64;


const int R = 10000000;
const int64 RR = (int64)R*R;
const int D = R + R;
double enip = 0;


/* abs(ad-bc)=1 */
double boy(int a, int b) {
	return __builtin_sqrt((double)a*a + (double)b * b);
}

uint64 prod(uint64 a, uint64 b, uint64 mod)
{
	return ((a*b) % mod);
}

uint64 apower(uint64 a, uint64 n, uint64 mod) {
	uint64 power = a;
	uint64 result = 1;

	while (n) {
		if (n % 2)
			result = prod(result, power, mod);
		power = prod(power, power, mod);
		n >>= 1;
	}
	return result;
}
uint64 kare(int n) {
	return (uint64)n*n;
}
int bul(int s, int t, int a, int b) { //{ {0,0},{s,t},{a,b} }
	int ha = a / 2, hb = b / 2;
	for (int i = 0; i <= 25; i++) {
		if (ha + i >= R) break;
		int g = __builtin_sqrt(0. + kare(R) - kare(ha + i));
		for (int j = 0; j <= hb-g; j++) {
			if (kare(ha + i) + kare(hb - j) <= kare(R) && kare(a - ha - i) + kare(b - hb + j) <= kare(R))
				return 1;
		}
		g = __builtin_sqrt(0. + kare(R) - kare(ha - i));
		for (int j = 1; j <= g - hb; j++) {
			if (kare(ha - i) + kare(hb + j) <= kare(R) && kare(a - ha + i) + kare(b - hb - j) <= kare(R))
				return 1;
		}
	}
	return 0;
}

uint64 f562()
{
	int phi[D + 7];
{
	phi[1] = 0;
	for (int i = 2; i <= D; i++) {
		if (!phi[i]) {
			phi[i] = i - 1;
			for (int j = i+i; j <= D; j += i) {
				if (!phi[j])
					phi[j] = j;
				phi[j] = (phi[j] / i) * (i - 1);
			}
		}
	}
}
	double eni = R;
	uint64 yan=0;
	for (int b = D - 1; b >= R; b--) {
		double da = __builtin_sqrt(kare(D) - kare(b));
		int a = da;
		if (a > b) break;
		double fark = D - boy(a, b), p;
		if (fark < eni && (a&1 || b&1)) {
			int s = apower(b, phi[a] - 1,a), t = ((uint64)s*b - 1) / a;
			if (bul(s,t,a,b)) {
				double peri = boy(a, b) + boy(s, t) + boy(a - s, b - t);
				eni = fark;
				double k1=boy(a,b), k2=boy(s,t), k3=boy(a-s,b-t);
				yan = 0.5 + k1*k2*k3/D;
				//printf("Bulunan: s: %d, t: %d, a: %d b: %d eni=%.15f peri=%.15f p:%llu\n", s, t, a, b, eni, peri,(uint64)p);
			}
		}
	}
	return yan;
}