HDU 5047 Sawtooth 高精度

题意：

给出一个\(n(0 \leq n \leq 10^{12})\)，问\(n\)个\(M\)形的折线最多可以把平面分成几部分。

分析：

很容易猜出来这种公式一定的关于\(n\)的一个二次多项式。

不妨设\(f(n)=an^2+bn+c\)。

结合样例我们可以列出\(3\)个方程：

\(f(0)=1,f(1)=2,f(2)=19\)

解出三个系数\(a,b,c\)，然后用高精度做即可。

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long LL;

const LL MOD = 1000000000;

struct Big

{

	LL a[5];

	Big() { memset(a, 0, sizeof(a)); }

	Big(LL x) { memset(a, 0, sizeof(a)); a[1] = x / MOD; a[0] = x % MOD; }

	void read() {

		memset(a, 0, sizeof(a));

		LL x; scanf("%lld", &x);

		a[0] = x % MOD; a[1] = x / MOD;

	}

	Big operator + (const Big& t) const {

		Big ans;

		for(int i = 0; i < 5; i++) ans.a[i] = a[i];

		for(int i = 0; i < 5; i++) {

			ans.a[i] += t.a[i];

			int j = i;

			while(ans.a[j] >= MOD) {

				ans.a[j + 1] += ans.a[j] / MOD;

				ans.a[j++] %= MOD;

			}

		}

		return ans;

	}

	Big operator * (const Big& t) const {

		Big ans;

		for(int i = 0; i < 5; i++) {

			for(int j = 0; j < 5; j++) if(i + j < 5) {

				ans.a[i + j] += a[j] * t.a[i];

				int k = i + j;

				while(ans.a[k] >= MOD) {

					ans.a[k + 1] += ans.a[k] / MOD;

					ans.a[k++] %= MOD;

				}

			}

		}

		return ans;

	}

	Big operator - (const Big& t) const {

		Big ans;

		for(int i = 0; i < 5; i++) ans.a[i] = a[i];

		for(int i = 0; i < 5; i++) {

			int j = i + 1;

			if(ans.a[i] < t.a[i]) {

				while(!ans.a[j]) j++;

				ans.a[j]--;

				for(int k = j - 1; k > i; k--) ans.a[k] += MOD - 1;

				ans.a[i] += MOD;

			}

			ans.a[i] -= t.a[i];

		}

		return ans;

	}

	void output() {

		int i = 0;

		for(i = 4; i; i--) if(a[i]) break;

		printf("%lld", a[i]);

		for(int j = i - 1; j >= 0; j--) printf("%09lld", a[j]);

		printf("\n");

	}

};

int main()

{

	int T; scanf("%d", &T);

	for(int kase = 1; kase <= T; kase++) {

		printf("Case #%d: ", kase);

		Big x; x.read();

		Big ans(1);

		ans = ans + (Big(8) * x * x);

		ans = ans - (Big(7) * x);

		ans.output();

	}

	return 0;

}

巴特西

HDU 5047 Sawtooth 高精度

题意：

分析：

最新文章

热门文章