[CF1497C2] k-LCM (hard version) - 构造
Description
给定一个整数 (n),请找到 (k) 个和为 (n) 的正整数 (a_1,a_2,dots,a_k),使得 (operatorname{lcm}{a_1,a_2,dots,a_k}leqslant dfrac n2) 。
(t) 组数据,(1leqslant tleqslant 10^4),(3leqslant nleqslant 10^9),(3leqslant kleqslant n)。保证所有 (t) 组数据中 (sum kleqslant 10^5)。
Solution
首先关于 easy version 也就是 (k le 3) 的情况,很容易 YY 出各种奇怪的做法
hard version 可以这样转化到 easy version:将 (n) 拆成 (n-k+3) 和 (k-3)
前面一部分按 easy version 的方法做
后面一部分直接拆成一堆 (1)
#include <bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
ios::sync_with_stdio(false);
int t;
cin >> t;
while (t--)
{
int n, k;
cin >> n >> k;
if (k == 3)
{
if (n & 1)
cout << 1 << " " << n / 2 << " " << n / 2 << endl;
else if (n % 4)
cout << 2 << " " << (n - 2) / 2 << " " << (n - 2) / 2 << endl;
else
cout << n / 4 << " " << n / 4 << " " << n / 2 << endl;
}
else
{
int _n = n - k + 3;
for (int i = 1; i <= k - 3; i++)
cout << 1 << " ";
{
int n = _n;
if (n & 1)
cout << 1 << " " << n / 2 << " " << n / 2 << endl;
else if (n % 4)
cout << 2 << " " << (n - 2) / 2 << " " << (n - 2) / 2 << endl;
else
cout << n / 4 << " " << n / 4 << " " << n / 2 << endl;
}
}
}
}