2018 Wannafly summer camp Day2--Utawarerumono
2018 Wannafly summer camp Day2--Utawarerumono
Utawarerumono 描述 题目描述： 算术是为数不多的会让久远感到棘手的事情。通常她会找哈克帮忙，但是哈克已经被她派去买东西了。于是她向你寻求帮助。
给出一个关于变量x,y的不定方程ax+by=cax+by=cax+by=c，显然这个方程可能有多个整数解。久远想知道如果有解，使得p2∗x2+p1∗x+q2∗y2+q1∗yp_2∗x^2+p_1∗x+q_2∗y^2+q_1∗yp2∗x2+p1∗x+q2∗y2+q1∗y最小的一组整数解是什么。为了方便，你只需要输出p2∗x2+p1∗x+q2∗y2+q1∗yp_2∗x^2+p_1∗x+q_2∗y^2+q_1∗yp2∗x2+p1∗x+q2∗y2+q1∗y的最小值。
输入： 第一行三个空格隔开的整数a,b,c(0≤a,b,c≤105)a,b,c(0≤a,b,c≤10^5)a,b,c(0≤a,b,c≤105)。
第二行两个空格隔开的整数p1,p2(1≤p1,p2≤105)p_1,p_2(1≤p_1,p_2≤10^5)p1,p2(1≤p1,p2≤105)。
第三行两个空格隔开的整数q1,q2(1≤q1,q2≤105)q_1,q_2(1≤q_1,q_2≤10^5)q1,q2(1≤q1,q2≤105)。
输出： 如果方程无整数解，输出``Kuon’’。
如果有整数解，输出p2∗x2+p1∗x+q2∗y2+q1∗yp2∗x^2+p1∗x+q2∗y^2+q1∗yp2∗x2+p1∗x+q2∗y2+q1∗y的最小值。
样例输入 2 2 1 1 1 1 1 样例输出 Kuon 由于一次项的影响较小，只考虑二次项p2∗x2+q1∗y2=p2∗((c−by)/a)2+q2∗y2p_2*x^2+q_1*y^2=p_2*((c-by)/a)^2+q_2*y^2p2∗x2+q1∗y2=p2∗((c−by)/a)2+q2∗y2,存在一个O(a)O(a)O(a)的∣y∣|y|∣y∣的取值满足c−byc-byc−by是一个aaa的倍数， 此时∣(c−by)/a∣|(c-by)/a|∣(c−by)/a∣是O(c+b)O(c+b)O(c+b)的，这样就得到了一组不超过101810^{18}1018的解，且答案不会更大。 后发现多项式的值在X的绝对值增加的时候，只有在x<0x<0x<0的时候才会变小,当x<(−p1)/2p2x<(-p_1)/2p_2x<(−p1)/2p2的值仍然会增大， 所以可以暴力枚举xxx或yyy的值(1e51e51e5就可以过了)。
#include <cstdio>
#include <cstring>
#include <cmath>
#include<algorithm>
#include<iostream>
using namespace std;
typedef long long ll;
ll p2,p1,q2,q1;
ll a, b, c, d, x, y;
ll ans=1e18;
ll Exgcd(ll a, ll b)
{
if(b==0){ x=1, y=0;return a;}
ll r = Exgcd(b, a%b);
ll tp=x;
x = y;
y = tp-a/b*y;
return r;
}
int main()
{
cin>>a>>b>>c>>p1>>p2>>q1>>q2;
d = Exgcd(a, b);
if(a==0&&b==0&&c==0) printf("0\n");
if(((a==0)&&(b==0)&&c) || c%d!=0 )
printf("Kuon\n");
else if(a&&b==0){
if(c%a!=0){
printf("Kuon\n");
}else{
ll ta=c/a;
ll ee=p2*ta*ta+p1*ta;
cout<<ee<<endl;
}
}
else if(a==0&&b)
{
if(c%b!=0)
printf("Kuon\n");
else{
ll tc=c/b;
ll eee=q2*tc*tc+q1*tc;
cout<<eee<<endl;
}
}
else{
for(int i=-100005;i<=100005;i++){
if((c-a*i)%b==0){
ll iy=(c-a*i)/b;
ll ac=p2*i*i+p1*i+q2*iy*iy+q1*iy;
ans=min(ans,ac);
}
}
cout<<ans<<endl;
}
return 0;
}腾讯云开发者
