#P15087. [UOI 2025 II Stage] Area of the Cake

    ID: 17003 远端评测题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 5 上传者: 标签>2025数论Special Judge最大公约数 gcdUOI(乌克兰)

[UOI 2025 II Stage] Area of the Cake

题目描述

Vus the Cossack and Us the Cossack are playing a game on a cake in the shape of a rectangle with dimensions n×mn \times m.

They take turns (Vus starts), cutting a square piece from the cake with the maximum possible side length such that three of the four sides of the square coincide with the sides of the cake at the beginning of the turn. The player then takes this piece for themselves. If the cake is square, the player takes the entire remaining cake.

:::align{center}

Cutting the cake 4×54 \times 5. The pieces of cake outlined in red are cut by Vus, and those in blue are cut by Us. :::

When the entire cake has been successfully divided, it turns out that the sum of the areas of the squares that Vus took is pp, and Us took qq.

The Cossacks got so caught up in the game that they forgot the size of the cake, so they asked you for help. Find any possible dimensions of the initial cake.

输入格式

The first line contains two integers pp and qq (0p,q1012;p+q>0)(0\leq p,q\leq10^{12}; p+q>0).

输出格式

Output two integers nn and mm --- the dimensions of the initial cake. If there are multiple correct answers, output any pair.

If such a cake does not exist, output 1-1.

18 2
4 5
4 0
2 2
8 3
-1

提示

An illustration of the first example is in the legend.

In the second example, a cake of size 2×22\times 2 satisfies the condition because then Vus will take the entire cake of area 44 on his first move.