CF1765M Minimum LCM
迪丽瓦拉
2024-03-03 04:08:44
0次
Problem - M - Codeforces
题意：
给定一个正整数n，让你求两个数a,b，使得a+b=n，且使得lcm(a,b)最小
思路：
关于lcm的一些结论：
1.若a是质数，则a和其他任意数的lcm就是其乘积
2.若a是合数，那么a和它的约数的lcm就是a
对于这道题，我们考虑a是合数的情况，当a是合数且n-a是a的约数时就是合法解，我们去找合法解的最优解
即我们要找到这样的a，使得a是合数，且a%(n-a)==0，统计这样的a的最大值
设小的数为a，大的数就是ka
a+ka=n
所以a是n的约数，因此我们去枚举约数就行，取最大的约数就行
Code：
#include
using namespace std;
#define int long long
int n,ans=1;
void solve(){ans=1;cin>>n;for(int i=2;i*i<=n;i++){if(n%i==0) ans=max(ans,n/i);}cout<>T;while(T--)solve();return 0;
} 总结：
关于lcm的一些结论：
1.若a是质数，则a和其他任意数的lcm就是其乘积
2.若a是合数，那么a和它的约数的lcm就是a
关于gcd的一些技巧：经常用到枚举gcd，设k倍的gcd这种小技巧，这样会好想一点