uva 10623 - Thinking Backward(数学)

本文主要是介绍uva 10623 - Thinking Backward(数学)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目链接：uva 10623 - Thinking Backward

题目大意：就是给出N，表示要将平面分解成N份，问有哪些可选则的方案，m表示椭圆、n表示圆形、p表示三角形的个数，m、n、p分别给定范围。

解题思路：本来这题一点思路都没有，但是在论坛上看到一个公式N=2+2m(m−1)+n(n−1)+4mn+3p(p−1)+6mp+6np

这样只要枚举m和p，求解n，判断n是否满足即可，注意n一定是整数。

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>using namespace std;
typedef  long long ll;
const int N = 100005;struct state {ll n, m, p;void set (ll m, ll n, ll p) {this->m = m;this->n = n;this->p = p;}
}s[N];bool cmp (const state& a,const state& b) {if (a.m != b.m)return a.m < b.m;if (a.n != b.n)return a.n < b.n;return a.p < b.p;
}int main () {int cas = 1;ll n;while (scanf("%lld", &n) == 1 && n != -1) {printf("Case %d:\n", cas++);if (n == 1) {printf("0 0 0\n");continue;}int c = 0;for (ll m = 0; m < 100; m++) {for (ll p = 0; p < 100; p++) {ll sum = 2 + 2 * m * (m-1) + 3 * p * (p-1) + 6 * m * p;sum = n - sum;ll a = 4 * m + 6 * p - 1;/*if (m == 0 && p == 0)printf("%lld %lld! \n", sum, a);*/double tmp = sum + a * a / 4.0;if (tmp < 0)continue;tmp = sqrt(tmp);double x = (tmp - ((double)a / 2.0));if (x < 0 || x >= 20000)continue;ll n = x;/**/if (n * n + a * n == sum)s[c++].set(m, n, p);}}sort (s, s + c, cmp);if (c) {for (int i = 0; i < c; i++)printf("%lld %lld %lld\n", s[i].m, s[i].n, s[i].p);} elseprintf("Impossible.\n");}return 0;
}