试题 算法训练 貌似化学
资源限制
时间限制：1.0s 内存限制：256.0MB
问题描述
现在有a,b,c三种原料，如果他们按x:y:z混合，就能产生一种神奇的物品d。
当然不一定只产生一份d，但a,b,c的最简比一定是x:y:z
现在给你3种可供选择的物品:
每个物品都是由a,b,c以一定比例组合成的，求出最少的物品数，使得他们能凑出整数个d物品（这里的最少是指三者个数的总和最少）
输入格式
第一行三个整数，表示d的配比（x,y,z）
接下来三行，表示三种物品的配比，每行三个整数（<=10000）。
输出格式
四个整数，分别表示在最少物品总数的前提下a,b,c,d的个数（d是由a,b,c配得的）
目标答案<=10000
如果不存在满足条件的方案，输出NONE
样例输入
3 4 5
1 2 3
3 7 1
2 1 2
样例输出
8 1 5 7
实现思路
假设已经知道了答案x, y , z；
存在这样的关系
(
x
y
z
)
∗
(
a
1
b
1
c
1
a
2
b
2
c
2
a
3
b
3
c
3
)
=
(
a
b
c
)
(x \ y \ z) * \begin{pmatrix} a1 & b1 & c1 \\ a2 &b2 & c2 \\ a3 &b3 & c3 \end{pmatrix} = (a \ b \ c)
(x y z)∗⎝⎛a1a2a3b1b2b3c1c2c3⎠⎞=(a b c)
那么 (x y z) 其实就可以通过逆矩阵求得
(
x
y
z
)
=
(
a
b
c
)
∗
(
a
1
b
1
c
1
a
2
b
2
c
2
a
3
b
3
c
3
)
−
1
(x \ y \ z) = (a \ b \ c) * \begin{pmatrix} a1 & b1 & c1 \\ a2 &b2 & c2 \\ a3&b3 & c3 \end{pmatrix} ^{-1}
(x y z)=(a b c)∗⎝⎛a1a2a3b1b2b3c1c2c3⎠⎞−1
实现代码
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
ll a[4][4], b[3][3], c[3], d[3];
ll gcd(ll a, ll b) { // 欧几里得求解最大公因子
if (a < b) swap(a, b);
if (b == 0) return a;
else return gcd(b, a % b);
}
void count() {
// 求逆矩阵
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
int minc, maxc, minr, maxr;
minc = min((i + 1) % 3, (i + 2) % 3), maxc = max((i + 1) % 3, (i + 2) % 3);
minr = min((j + 1) % 3, (j + 2) % 3), maxr = max((j + 1) % 3, (j + 2) % 3);
b[i][j] = pow (-1, i + j) * (a[minr][minc] * a[maxr][maxc] - a[maxr][minc] * a[minr][maxc]);
}
}
//求解待解矩阵
for (int i = 0; i < 3; i++) d[i] = b[0][i] * c[0] + b[1][i] * c[1] + b[2][i] * c[2];
if (d[0] < 0 || d[1] < 0 || d[2] < 0) d[0] = -d[0], d[1] = -d[1], d[2] = -d[2];
if (d[1] < 0 || d[2] < 0) cout << "NONE" << endl; // 若存在不同号，则现实中不存在负数的量，即不存在
else {
ll temp = gcd(d[0], d[1]); temp = gcd(temp, d[2]);
ll ans = 0;
for (int i = 0; i < 3; i++) d[i] /= temp;
for (int i = 0; i < 3; i++) ans += d[i] * a[i][0];
ans /= c[0];
cout << d[0] << " " << d[1] << " " << d[2] << " " << ans << endl;
}
}
int main() {
for (int i = 0; i < 3; i++) cin >> c[i];
for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) cin >> a[i][j];
count();
return 0;
}
