0%

牛客国庆集训派对Day1 - Utawarerumono

题目链接


题目描述

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

输入描述

第一行三个空格隔开的整数$a,b,c$($1 \leq a, b, c \leq 10^5$)。
第二行两个空格隔开的整数$p_1,p_2$($1 \leq p_1, p_2 \leq 10^5$)。
第三行两个空格隔开的整数$q_1,q_2$($1 \leq q_1, q_2 \leq 10^5$)。

输出描述

如果方程无整数解,输出”Kuon”。
如果有整数解,输出$p_2x^2+p_1x+q_2y^2+q_1y$的最小值。

示例1

输入

2 2 1
1 1
1 1

输出

Kuon

示例2

输入

1 2 3
1 1
1 1

输出

4

Solution

原题当中说的是a,b,c可以等于0,但经过我的测试发现没有,那就不管了吧。。。

我们知道$ax+by=c$有解当且仅当$(a,b) \vert c$。这里的$a,b,c$都要是正整数。
可以用扩展欧几里得算法求出一对特解$x_0,y_0$使得$ax_0+by_0=c$成立。然后其余解$x,y$都有$x \equiv x0\ (mod\ b),\ y=\frac{c-ax}{b}$。
那么我们可以用恒等式来转换原式:

$$p_2x^2+p_1x+q_2y^2+q_1y$$
$$=p_2x^2+p_1x+q_2(\frac{c-ax}{b})^2+q_1\frac{c-ax}{b}$$
$$=(\frac{a^2}{b^2}q_2+p_2)x^2+(p_1-\frac{a}{b}q_1-\frac{2acq_2}{b^2})x+\frac{cq_2}{b^2}$$

令$A=\frac{a^2}{b^2}q_2+p_2,\ B=p_1-\frac{a}{b}q_1-\frac{2acq_2}{b^2}$,则该函数最低点为:
$$x=-\frac{B}{2A}=-\frac{p_1-\frac{a}{b}q_1-\frac{2acq_2}{b^2}}{2(\frac{a^2}{b^2}q_2+p_2)}$$

当然啦,这个x很有可能不是整数,而且它的x也不一定满足规则,这时候我们需要找到最近的左右各一个的满足条件的点。即利用$x \equiv x0\ (mod\ b)$的特点来找。可以暴力找O(b)和数学方法O(1)找都可以。而且记住利用扩展欧几里得算出来的x和y有可能有负数。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
def exgcd(x, y):
if y == 0:
return 1, 0
a, b = exgcd(y, x % y)
return b, a - x // y * b

def get(dow, b, x):
def toPlus(n, p):
return ((n % p) + p) % p
i = int(dow) // b * b + toPlus(x, b)
if dow > i:
return i, i + b
return i, i - b

def calc(x, p1, p2, q1, q2, a, b, c):
y = (c - a * x) // b
ret = p2 * x * x + p1 * x + q2 * y * y + q1 * y
return ret

def main():
a, b, c = map(int, input().split())
p1, p2 = map(int, input().split())
q1, q2 = map(int, input().split())
x, y = exgcd(a, b)
gcd = a * x + b * y
if c % gcd != 0:
print('Kuon')
else:
a, b, c = a // gcd, b // gcd, c // gcd
x *= c
dow = (-p1 + a / b * q1 + 2 * a * c * q2 / (b * b)) / (2 * (a * a * q2 / (b * b) + p2))
i, j = get(dow, b, x)
ans = min(calc(i, p1, p2, q1, q2, a, b, c), calc(j, p1, p2, q1, q2, a, b, c))
print(ans)

if __name__ == '__main__':
main()

题目链接
回到开头