CF1372B - Omkar and Last Class of Math（源地址自⇔CF1372B）

Problem

Example

3
4
6
9

2 2
3 3
3 6

tag：

⇔贪心、⇔数学规律、⇔数论、⇔*1300

题意：

将题目给定的 \(c\) 拆分成 \(a+b=c\)，求出使得 \(LCM(a,b)\) 最大的 \(a\) 与 \(b\)。

思路：

暴力打表寻找规律，发现对于偶数 \(n\)，答案恒为 cout<<n/2<<" "<<n/2<<endl; （最大的 \(LCM(a,b)\) 即为 \(\frac{n}{2}\)）；对于奇数 \(n\)，答案恒为 \(n\) 最小的因数 \(x\) 与 \(n-x\) ，即 cout<<divi(n)<<" "<<n-divi(n)<<endl; 。

证明不详。

AC代码：

//A WIDA Project
#include<bits/stdc++.h>
using namespace std;
#define LL			long long
//===============================================================
LL T,ans,n;
//===============================================================
LL divi(LL n){
	for(LL i=2;i*i<=n;i++){
		if(n%i==0){
			ans=i;
			return ans;
		}
	}
	return 0;
}
int main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0)
	cin>>T;
	while(T-->0){
		ans=0;
		cin>>n;
		if(n%2==0) cout<<n/2<<" "<<n/2<<endl;
		else{
			ans=divi(n);
			if(ans==0) cout<<1<<" "<<n-1<<endl;
			else cout<<n/ans<<" "<<n-n/ans<<endl;
		}
	}
	return 0;
}

错误次数：2次

原因：分解因数没有优化到 \(O(\sqrt{n})\) ，导致超时。

原因：未考虑给定的数字是质数的情况（最小因数为1，这种情况代码中ans=0），导致除以0的情况发生，RE一次。

---

文 / WIDA
2021.10.14成文
首发于WIDA个人博客，仅供学习讨论

---

更新日记：
2021.10.14 成文