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;
}
评论
登录后参与技术讨论,分享你的经验与见解。
登录 / 注册暂无评论