Problem A. Restoring Numbers
Pavel had two positive integers a and b. He found their sum s and greatest common divisor g,
and forgot a and b after that. Help him to restore the original numbers.
Input
A single line contains two integers s and g (1 ≤ s ≤ 10^9, 1 ≤ g ≤ 10^9) — sum and greatest common
divisor of the numbers a and b.
Output
If Pavel made a mistake and there are no such numbers a and b, output a single number - 1.
Otherwise, output two positive integers a and b on a single line, separated by a space. If there are
multiple possible solutions, output any of them.
手工翻译
Pavel 有两个正整数a和b，他发现他们的和s和最大公约数g并且在那之后忘记了a和b帮助他恢复原来的数字。
输入
一行包含s和g的数是a和b的最大公约数
输出
要是能有这个a和b就输出a和b不然就输出-1
考试时的代码
#include <iostream>
using namespace std;
long long gcd(long long a, long long b) {
return b ? gcd(b, a % b) : a;
}
int main() {
long long s, m;
cin >> s >> m;
for (long long i = 1; i <= s / 2; i++) {
if (gcd(i, s - i) == m) {
cout << s-i << ' ' << i;
return 0;
}
}
cout << -1;
return 0;
}
这个代码很显然是暴力，我们对其进行时间复杂度的分析，大约是5*10^8,所以就会像考试是一样在21个点时超时。所以我们对其进行分析
#include <cstdio>
int sum, gcd;
int main () {
scanf ("%d%d", &sum, &gcd);
if (sum % gcd != 0 || sum == gcd) {
printf ("-1");
return 0;
}
sum /= gcd;
printf ("%d %d", (sum - 1) * gcd, gcd);
return 0;
}