#关于最小公倍数 题意描述:
对于一个正数n,求两个数a,b,使得a+b=n。在许多组ab中,选ab最小公倍数最小的那一组。
原始思路:
遍历1到n-1,使用双指针ij,一头一尾,朝中间走,不断循环,循环终止条件为i>j.这里的ij指向就是对应的ab,然后记录当前的最小公倍数,与上一次的最小公倍数比较,去小值。循环完后就留下最小的那一组。
在双指针,移动到中间时,有两种情况,n-1为奇数时,i=j。n-1为偶数时,i=j-1.所以终止条件才为i>j.
结果:
超时了。
新思路:
#include<iostream>
#include<math.h>
#include<algorithm>
using namespace std;
int main() {
int t, n;
cin >> t;
while (t--) {
cin >> n;
int x = 1;
for (int i = 2; i <= sqrt(n); i++) {
if (n % i == 0) {
x = n / i;
break;
}
}
cout << x << " " << n - x << endl;
}
return 0;
}
找到除1以外第一个能被n整除的数i,求得数x=n/i。 x与n-x就是要求得那组ab。 但我还是有疑惑,不知原理