链接：https://www.nowcoder.com/acm/contest/201/C
来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 1048576K，其他语言2097152K
64bit IO Format: %lld

题目描述

算术是为数不多的会让Kuon感到棘手的事情。通常她会找Haku帮忙，但是Haku已经被她派去买东西了。于是她向你寻求帮助。
给出一个关于变量x,y的不定方程ax+by=c，显然这个方程可能有多个整数解。Kuon想知道如果有解，使得p2*x2+p1*x+q2*y2+q1*y最小的一组整数解是什么。为了方便，你只需要输出p2*x2+p1*x+q2*y2+q1*y的最小值。

输入描述

第一行三个空格隔开的整数a,b,c(0 ≤ a,b,c≤ 10^5)。 第二行两个空格隔开的整数p1,p2(1 ≤ p1,p2 ≤ 10^5)。 第三行两个空格隔开的整数q1,q2(1 ≤ q1,q2 ≤ 10^5)。

输出描述

如果方程无整数解，输出“Kuon”。 如果有整数解，输出p2*x2+p1*x+q2*y2+q1*y的最小值。

 

样例输入

2 2 1
1 1
1 1
1 2 3
1 1
1 1

样例输出

Kuon
4

解题思路

直接暴力解方程ax+by=c，求出p2*x2+p1*x+q2*y2+q1*y最小的那一个。考虑一些无解和其它的一些特殊情况，具体见代码：

#include <iostream>
#include <algorithm>
using namespace std;
const long long inf = 1e18;
long long p2, p1, q2, q1,a, b, c, d, xx, yy, minn;
long long gcd(long long a, long long b)
{
    if (!b)
        return a;
    return gcd(b, a % b);
}
int main()
{
    long long x, y, ans;
    while (cin >> a >> b >> c >> p1 >> p2 >> q1 >> q2)
    {
    	minn = inf;
        d = gcd(a, b);
        if (!a && !b && !c)
            printf("0\n");
        else if (!a && !b && c || c % d)
            printf("Kuon\n");
        else if (a && !b)
        {
            if (c % a)
                printf("Kuon\n");
            else
            {
                x = c / a;
                ans = p2 * x * x + p1 * x;
                cout << ans << endl;
            }
        }
        else if (!a && b)
        {
            if (c % b)
                printf("Kuon\n");
            else
            {
                y = c / b;
                ans = q2 * y * y + q1 * y;
                cout << ans << endl;
            }
        }
        else
        {
            for(int xi = -100000; xi <= 100000; xi++)
            {
                if((c - a * xi) % b == 0)
                {
                    long long yi = (c - a * xi) / b;
                    ans = p2 * xi * xi + p1 * xi + q2 * yi * yi + q1 * yi;
                    minn = min(ans, minn);
                }
            }
            cout << minn << endl;
        }
    }
    return 0;
}