#关于最小公倍数 题意描述:

对于一个正数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。 但我还是有疑惑,不知原理