ZOJ Monthly, November 2010解题报告 » ZOJ3428

ZOJ3428
ZOJ3428.cpp


#include <cstdio>
#include <vector>
#include <utility>
#include <cassert>
#include <algorithm>

using namespace std;

const int LIMIT = 1000001;
const int RLIMIT = 1600;

template<typename T>
inline T gcd(T a, T b) {
	return b == 0 ? a : gcd(b, a % b);
}

struct BigInt {
	static const long long MOD = 1000000000000000000LL;
	long long h, l;

	BigInt() : h(0), l(0) {
	}

	void add(long long x) {
		l += x;
		while (l >= MOD) {
			l -= MOD;
			++h;
		}
	}

	void print(long long x) {
		if (x == 0) {
			printf("NaN");
			return;
		}
		long long g = gcd((h % x) * (MOD % x) + l, x);
		long long hh = h / g;
		long long ll = (h % g) * (MOD / g) + ((h % g) * (MOD % g) + l) / g;
		if (hh > 0) {
			printf("%lld%018lld/%lld", hh, ll, x / g);
		} else {
			printf("%lld/%lld", ll, x / g);
		}
	}
};

// r=first; s=second
// x=r^2-s^2; y=2rs; z=r^2+s^2
// vector<pair<int, int> > pythagoras;
// static BigInt a[LIMIT];
// static BigInt b[LIMIT];
// static long long c[LIMIT];

static struct ABC {
	BigInt a, b;
	long long c;
} abc[LIMIT];

inline long long sum2(long long n) {	// \sum_{i=0}^n{i^2}
	return n * (n + 1) / 2 * (n + n + 1) / 3;
}

inline void gao(long long x, long long y) {
	long long l = max(1LL, x - y);
	long long r = x / 2 + 1;
	if (l < r) {
		abc[y].a.add((x * x + y * y) * (r - l));
		abc[y].b.add(sum2(r - 1) - sum2(l - 1));
		abc[y].b.add(sum2(x - l) - sum2(x - r));
		abc[y].b.add((y * y) * (r - l));
		abc[y].c += r - l;
	}
}

void init() {
	// pythagoras
	for (int r = 1; r < RLIMIT; ++r) {
		for (int s = r % 2 + 1; s < r; s += 2) {
			if (gcd(r, s) == 1) {
				int x = r * r - s * s;
				int y = 2 * r * s;
				if (x > y) {
					swap(x, y);
				}
				for (long long i = x, j = y; i < LIMIT; i += x, j += y) {
				//	pythagoras.push_back(make_pair(i, j));
					if (j < LIMIT) {
						gao(i, j);
					}
					gao(j, i);
				}
			}
		}
	}
	// printf("%d\n", pythagoras.size());	// 2388959
}

int main() {
	int n = 0;

	init();
	while (scanf("%d", &n) != EOF) {
		assert(1 <= n && n <= 1000000);
		abc[n].a.print(abc[n].c);
		putchar(' ');
		abc[n].b.print(abc[n].c);
		puts("");
	}

	return 0;
}

//Run ID 	Submit Time 	Judge Status 	Problem ID 	Language 	Run Time(ms) 	Run Memory(KB) 	User Name 	Admin
//404 	2010-11-11 23:17:38 	Accepted 	B 	C++ 	2520 	39244 	watashi@Zodiac 	Source
Leave a Reply