Utawarerumono——————暴力

电玩女神 2022-05-09 05:58 154阅读 0赞

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

**题目描述**  
算术是为数不多的会让Kuon感到棘手的事情。通常她会找Haku帮忙，但是Haku已经被她派去买东西了。于是她向你寻求帮助。  
给出一个关于变量x,y的不定方程ax+by=c，显然这个方程可能有多个整数解。Kuon想知道如果有解  
使得 p 2 ∗ x 2 + p 1 ∗ x + q 2 ∗ y 2 + q 1 ∗ y p2\*x2+p1\*x+q2\*y2+q1\*y p2∗x2\+p1∗x\+q2∗y2\+q1∗y最小的一组整数解是什么。  
为了方便，你只需要输出 p 2 ∗ x 2 + p 1 ∗ x + q 2 ∗ y 2 + q 1 ∗ y p2\*x2+p1\*x+q2\*y2+q1\*y p2∗x2\+p1∗x\+q2∗y2\+q1∗y的最小值。  
**输入描述:**  
第一行三个空格隔开的整数 a , b , c ( 0 ≤ a , b , c ≤ 1 0 5 ) a,b,c(0 ≤ a,b,c≤ 10^5) a,b,c(0≤a,b,c≤105)。  
第二行两个空格隔开的整数 p 1 , p 2 ( 1 ≤ p 1 , p 2 ≤ 1 0 5 ) p1,p2(1 ≤ p1,p2 ≤ 10^5) p1,p2(1≤p1,p2≤105)。  
第三行两个空格隔开的整数 q 1 , q 2 ( 1 ≤ q 1 , q 2 ≤ 1 0 5 ) q1,q2(1 ≤ q1,q2 ≤ 10^5) q1,q2(1≤q1,q2≤105)。  
**输出描述:**  
如果方程无整数解，输出“Kuon”。  
如果有整数解，输出 p 2 ∗ x 2 + p 1 ∗ x + q 2 ∗ y 2 + q 1 ∗ y p2\*x2+p1\*x+q2\*y2+q1\*y p2∗x2\+p1∗x\+q2∗y2\+q1∗y的最小值。  
**示例1**  
输入  
2 2 1  
1 1  
1 1

输出  
Kuon

**示例2**  
输入  
1 2 3  
1 1  
1 1

输出  
4

--------------------

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const ll maxn = 2e5+7;
    const ll INF = 0x3f3f3f3f3f3f3f3f;
    ll a,b,c,p1,p2,q1,q2;
    int main()
    {
        
            while(~scanf("%lld %lld %lld %lld %lld %lld %lld",&a,&b,&c,&p1,&p2,&q1,&q2))
            {
        
                    ll ans= INF;
                    for(ll i=-maxn;i<maxn;i++)
                    {
        
                            ll x=(c-b*i)/a;
                            if(x*a+i*b!=c)  continue;
                            ll mid=p2*x*x+p1*x+q2*i*i+q1*i;
                            ans=min(mid,ans);
                    }
                    if(ans==INF)    puts("Kuon");
                    else            printf("%lld\n",ans);
            }
            return 0;
    }

[https_www.nowcoder.com_acm_contest_201_C]: https://www.nowcoder.com/acm/contest/201/C