Preliminaries for Benelux Algorithm Programming Contest 2019 - F.Floor Plan

原题面

描述

You are an architect and you have just been appointed to build a new swimming hall. The organisation behind these plans has acquired funding for a swimming pool and surrounding building as large as they want, but unfortunately they could not find anyone willing to pay for the floor surrounding the pool. They decided to pay for the floor tiles out of their own pocket. Because this has already cost them an arm and a leg, they want you to use all the floor tiles in your proposed plan.
Being an architect, you care for aesthetics. You see it as absolutely vital that both the swimming pool and the surrounding building are perfect squares. This raises an interesting problem: how can you make sure that the square shapes are guaranteed, while still using all the floor tiles the organisation bought?
Given the number of tiles , find the length of the side of the building and the length of the side of the pool such that , or print impossible if no suitable and exist.

输入

One line containing a single integer .

输出

Print two non-negative integers , such that , or print impossible if no such integers exist. If there are multiple valid solutions, you may output any one of them.

数据范围

For all case, and .

时空限制

• 时间限制：
• 空间限制：

样例

输入	输出
7	4 3
10	impossible
15	4 1

链接

• https://nanti.jisuanke.com/t/43470

题解

题意

给定正整数，求任意一组满足的正整数和。

思路

• 考虑。
• 令，，，其中。
• 枚举，求得，再判断与是否为整数即可。

时间复杂度

代码

#include <cstdio>
int n, x, y;
int main() {
    scanf("%d", &n);
    for (int i = 1; i * i <= n; ++i)
        if (n % i == 0) {
            x = i;
            y = n / i;
            if ((y + x) % 2 == 0 && (y - x) % 2 == 0) {
                printf("%d %d\n", (y + x) / 2, (y - x) / 2);
                return 0;
            }
        }
    printf("impossible\n");
    return 0;
}