求一个最小的正整数x，使得(y + x) (y - x) = n成立
考虑一下n的分解因式。
可能会想到枚举n的约数，那么a * b = n成立，取最小的x即可
但是要枚举到n / 2，这样会超时。
因为要使得a * b = n，那么a和b中最大的数字最多是sqrt(n)，因为不可能是两个大于sqrt(n)的数字相乘得到n的（大过n了）
所以我可以枚举 1 -- sqrt(n)中n的约数，得到a和b，然后反转一下a和b，就是所有a * b = n的结果
例如18的约数
1、2、3、6、9、18
枚举到sqrt(18) = 4即可
当然这题不用反转。
#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <algorithm> using namespace std; #define inf (0x3f3f3f3f) typedef long long int LL; #include <iostream> #include <sstream> #include <vector> #include <set> #include <map> #include <queue> #include <string> void work() { int n; scanf("%d", &n); int t = sqrt(n * 1.0); int ans = inf; for (int i = 1; i <= t; ++i) { if (n % i != 0) continue; int a = n / i; int b = i; if ((a - b) & 1) continue; if (a == b) continue; ans = min(ans, (a - b) / 2); } if (ans == inf) { printf("-1 "); } else { printf("%d ", ans); } return; } int main() { #ifdef local freopen("data.txt","r",stdin); #endif int t; scanf("%d", &t); while (t--) { work(); } return 0; }