您好,欢迎访问代理记账网站
  • 价格透明
  • 信息保密
  • 进度掌控
  • 售后无忧

k-LCM (easy version) CodeForces - 1497C1(思维+构造/n分奇偶)

It is the easy version of the problem. The only difference is that in this version k=3.

You are given a positive integer n. Find k positive integers a1,a2,…,ak, such that:

a1+a2+…+ak=n
LCM(a1,a2,…,ak)≤n2
Here LCM is the least common multiple of numbers a1,a2,…,ak.

We can show that for given constraints the answer always exists.

Input

The first line contains a single integer t (1≤t≤104) — the number of test cases.

The only line of each test case contains two integers n, k (3≤n≤109, k=3).

Output

For each test case print k positive integers a1,a2,…,ak, for which all conditions are satisfied.

Example Input

3
3 3
8 3
14 3

Output

1 1 1
4 2 2
2 6 6

题意:简单版本k=3。给你一个正整数n,找出3个正整数满足:

1、a1+a2+a3=n;

2、LCM(a1,a2,…,ak)≤n/2,即a1、a2、a3的最小公倍数<=n/2;

题解:1、当n为奇数的时候可以分成:1、n/2、n/2;

2、n为偶数,可以把a1=2或2的倍数,a2=(n-a1)/2,a3=a2,接下来只需要判断LCM(a1,a2)<=n/2即可,符合就输出。

g=__gcd(i,h);//注意不能交c++!!!

AC代码:

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<algorithm>
using namespace std;
typedef long long ll;
int main()
{
	ll t,n,k;
	scanf("%lld",&t);
	while(t--)
	{
		scanf("%lld%lld",&n,&k);
		if(n%2!=0)
			printf("1 %lld %lld\n",n/2,n/2);
		else
		{
			ll i,h,g,u;
			for(i=2;; i=i*2)
			{
				h=n-i;
				h=h/2;
				g=__gcd(i,h);//注意不能交c++
				u=(h*i)/g;
				if(u<=n/2)
				{
					printf("%lld %lld %lld\n",i,h,h);
					break;
				}
			}
		}
	}
	return 0;
}

分享:

低价透明

统一报价,无隐形消费

金牌服务

一对一专属顾问7*24小时金牌服务

信息保密

个人信息安全有保障

售后无忧

服务出问题客服经理全程跟进