题目
链接
给出方程组:$$\displaystyle \left\{\begin{aligned}11x + 13y + 17z = 2471 \\13x + 17y + 11z = 2739\end{aligned}\right.$$ 已知 $x$,$y$,$z$ 均为正整数, 请你计算 $x$,$y$,$z$ 相加之和的最小值
解决方法
由空间几何知, 方程组确定的是一条直线, 加上正整数约束就是一条线段, 求线段上的点 $x+y+z$ 的最小值.
确定其中一个可求出另外两个, 枚举其中范围较小的,$1 \leq z \leq 2471 / 17=145 $.
- #include<bits/stdc++.h>
- using namespace std;
- //11x+13y=2471-17z=m
- //13x+17y=2739-11z=n
- bool get_xy(int z, int& x, int& y)
- {
- int m = 2471 - 17 * z;
- int n = 2739 - 11 * z;
- int tmp1 = 11 * n - 13 * m;
- int tmp2 = n - m;
- if(tmp1 % 18) return false;
- if(tmp2 % 2) return false;
- y = tmp1 / 18;
- x = tmp2 / 2 - 2 * y;
- if(x < 1 || y < 1) return false;
- return true;
- }
- int main()
- {
- int maxx = 2471;
- int x, y;
- for(int z = 1;z < 150;z++)
- {
- if(get_xy(z, x, y))
- {
- //printf("%d %d %d %d\n", x, y, z, x+y+z);
- if((x + y + z) < maxx)
- {
- maxx = x + y + z;
- }
- }
- }
- printf("%d\n", maxx);
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3113553.html