题解 CF1497C2 【k-LCM (hard version)】

posted on 2021-03-20 09:09:40 | under 题解 | source

2023 编者注：有一些链接点不进去，分别是 cf1497c1 的 cf 页面和 https://www.cnblogs.com/caijianhong/p/Solution-cf1497c1.html

此题与 CF1497C1 有异曲同工之妙。

我们知道，\(\operatorname{lcm}(1,x)=x\)，不难想到，\(\operatorname{lcm}(1,1,...,1,x)\) 也等于 \(x\)，有多少个 \(1\) 不影响结果。那么我们可以输出 \(k-3\) 个 \(1\)，并将 \(n\) 减去 \(k-3\)，然后按照 CF1497C1 中 \(k=3\) 的情况处理即可。

int n,k;
int mian(){
	scanf("%d%d",&n,&k);
	while(k>3) n--,k--,printf("1 ");//while循环更容易理解
	if(n&1) printf("%d %d 1",n/2,n/2);
	else if(n%4==0) printf("%d %d %d",n/2,n/4,n/4);
	else printf("%d %d 2",n/2-1,n/2-1);
	return puts(""),0;
}