暑期训练day5 B. Omkar and Last Class of Math

2021/7/19 6:09:20

本文主要是介绍暑期训练day5 B. Omkar and Last Class of Math,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

一.题意

在40的最后一节数学课上,他学习了最小公倍数(LCM)。LCM(a,b)是可被a和b整除的最小正整数x。

Omkar有一个值得称赞的好奇心,他立刻想到了一个涉及LCM运算的问题:给定一个整数n,找到正整数a和b,使得a+b=n,LCM(a,b)是可能的最小值。

你能40解决他的数学难题吗?

 二.输入输出

输入

每个测试包含多个测试用例。第一行包含测试用例的数量t(1≤T≤10). 测试用例的描述如下。

每个测试用例由一个整数n组成(2≤N≤10^9).

输出

对于每个测试用例,输出两个正整数a和b,这样a+b=n,LCM(a,b)是最小可能值。

三.思路

这两个整数是k和n−k、 其中k是n的最大固有因子

四.上板子
 

#include<iostream>
#include<map>
typedef long long ll;
using namespace std;
ll gcd(ll a, ll b)
{
	return a % b == 0 ? b : gcd(b, a % b);
}
ll lcm(ll a, ll b)
{
	return a / gcd(a, b) * b;
}
int main()
{
	ll n;
	int t;
	cin >> t;
	while (t--)
	{
		cin >> n;
		ll max = 0;
		ll x = 0;
		ll y = 0;
		ll k = 1e5;
		for (int i = 1; i <= n / 2; i++)
		{
			if (n % i == 0&&i>=max)
			{
				max = i;
			}
		}
		if (max >= n - max)
		{
			cout << n - max << " " << max << endl;
		}
		else
		{
			cout << max << " " << n - max << endl;
		}
	}
	return 0;
}



这篇关于暑期训练day5 B. Omkar and Last Class of Math的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程