B. Omkar and Last Class of Math 思维lcm

题意

  给你一个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。

AC代码

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;

}

评论

暂无评论