给你一个n，要求给出两个整数a和b，使得a+b=n且lcm(a,b)最小。
结论：答案是k和n-k，k为n的最大真因子。
证明：假设a<=b，则lcm>=b，取最小则自然是lcm==b，lcm>b，最小的就是2b，2b>n故舍去，所以我们要构造lcm=b的解。
lcm=b故a整除b，则b=ma，所以a+ma=n，故a整除n。现在lcm=b，a是n的因子，我们让lcm尽可能小，故让a尽可能大，b尽可能小。
所以我们找n的最大真因子，如果找不到那就是说明n是质数，a=1。
#include<iostream> #include<stdio.h> using namespace std; int t,n; bool isp(int x){ for(int i=2;i*i<=n;i++){ if(n%i==0) return 0; } return 1; } int main() { scanf("%d",&t); while(t--) { scanf("%d",&n); int a=1; for(int i=2;i*i<=n;i++){ if(n%i==0){ a=n/i; break; } } cout<<a<<" "<<n-a<<‘\n‘; } return 0; }
B. Omkar and Last Class of Math 思维lcm
原文：https://www.cnblogs.com/qq2210446939/p/13298475.html