---

题目描述

输入

输出

样例输入

2 3 1

样例输出

2.5

---

解题思路

为了方便，我们把$ma$ma记作$a$a，把$mb$mb记作$b$b，把$P$P记作$c$c，那么题目就变成了：
已知$a,b,c$a,b,c，求$ax+by=c$ax+by=c的一组解，使得$0.5*a*x^2+0.5*b*y^2$0.5∗a∗x2+0.5∗b∗y2最小，输出这个最小值
显然，第一步我们用拓展欧几里得算法求出这个不定方程的一组特解，为$\begin{cases}x_0 \\ y_0 \\ \end{cases}${x0​y0​​，令$a$a和$b$b的最大公因数为$d$d，那么通解为$\begin{cases}x_1=x_0+\frac{b}{d}t \\ y_1=y_0-\frac{a}{d}t\\ \end{cases}${x1​=x0​+db​ty1​=y0​−da​t​
所以$ans=0.5(ax_1^2+by_1^2)$ans=0.5(ax12​+by12​)将$x_1=x_0+\frac{b}{d}t$x1​=x0​+db​t和$y_1=y_0-\frac{a}{d}t$y1​=y0​−da​t代入这个式子化简后可得：$ans=0.5(\frac{a+b}{d^2}abt^2+2\frac{ab(x_0-y_0)}{d}t+ax_0^2+by_0^2)$ans=0.5(d2a+b​abt2+2dab(x0​−y0​)​t+ax02​+by02​)
这就是一个关于$t$t的二次函数，对称轴为：$t_1=-\frac{\frac{ab(x_0-y_0)}{d}}{\frac{a+b}{d^2}ab}=\frac{(y_0-x_0)d}{a+b}$t1​=−d2a+b​abdab(x0​−y0​)​​=a+b(y0​−x0​)d​
再在$t_1$t1​两边的两个整点（也就是$\lfloor t1 \rfloor$⌊t1⌋和$\lfloor t1 \rfloor+1$⌊t1⌋+1）中去找答案即可

---

参考代码

#include <cstdio>
#include <cstring>
#include <cmath>
#define reg register
 
template <class T>
inline T read() {
    T x = 0; T f = 1; char s = getchar();
    while(s < '0' || s > '9') {if(s == '-') f = -1; s = getchar();}
    while(s >= '0' && s <= '9') {x = (x << 3) + (x << 1) + s - 48; s = getchar();}
    return x * f;
}
 
template <typename T>
inline void wri(T x) {
    if(x < 0) {x = -x; putchar('-');}
    if(x / 10) wri(x / 10);
    putchar(x % 10 + 48);
}
 
template <typename T>
inline void write(T x, char s) {
    wri(x);
    putchar(s);
}
 
template <typename T>
inline T Min(T x, T y) {return x < y ? x : y;}
 
#define LL long long
 
int ma, mb, p, gcd;
double va, vb, t, tmp, pa, pb, ans;
 
inline int exgcd(int a, int b, double &x, double &y) {	//拓展欧几里得算法
    if(! b) {
        x = 1, y = 0;
        return a;
    }
    else {
        int tmp = exgcd(b, a % b, y, x);
        y -= x * (a / b);
        return tmp;
    }
}
 
int main() {
    ma = read<int>(), mb = read<int>(), p = read<int>();
    gcd = exgcd(ma, mb, va, vb);
    va *= (p * 1.0 / gcd), vb *= (p * 1.0 / gcd);	//算出特解
    if(p % gcd != 0) {	//判断无解
        puts("-1");
        return 0;
    }
    t = (vb - va) * gcd * 1.0 / (ma + mb);	//算出t1并在两边找答案
    tmp = floor(t);
    pa = va + tmp * (mb / gcd);
    pb = vb - tmp * (ma / gcd);
    ans = 0.5 * ma * pa * pa + 0.5 * mb * pb * pb;
    tmp = floor(t) + 1;
    pa = va + tmp * (mb / gcd);
    pb = vb - tmp * (ma / gcd);
    ans = Min(ans, 0.5 * ma * pa * pa + 0.5 * mb * pb * pb);
    LL q = ans;	//判断是否为浮点数
    if(ans != q)
        printf("%.1lf\n", ans);
    else
        write(q, '\n');
    return 0;
}