[codeforces 1372 B] Omkar and Last Class of Math 수의 분할

1121 단어 codeforces
Codeforces Round #655 (Div. 2)   참여 랭 킹 인원수 15842   매일 밤 을 새 워 경 기 를 하 는데, 몸 이 견 딜 수 없어 서, 행복 감 이 가득 한 결정 을 내 렸 고, 경기 후 다음날 다시 닦 았 다.
[codeforces 1372B]    Omkar and Last Class of Math   수의 분할
목록https://blog.csdn.net/mrcrack/article/details/103564004
온라인 평가 주소http://codeforces.com/contest/1372/problem/B
Problem
Lang
Verdict
Time
Memory
B - Omkar and Last Class of Math
GNU C++17
Accepted
31 ms
3900 KB
제목: n 을 세 고 a + b = n 을 찾 습 니 다. 해당 하 는 LCM (a, b) 이 가장 작 아야 합 니 다.
기본 사고방식: 수 를 나 누고,
1. n 이 질 수 라면 두 가지 로 나눈다. 1, n - 1
2. n 이 소수 가 아니라면
k>=2,
n=k*a,a=n/k.
a=a,
b=n-a=k*a-a=(k-1)*a=(k-1)*n/k.
최소 공배수 b = (1 - 1 / k) * n, 요구 b 최소, 그러므로 k 최소.
AC 코드 는 다음 과 같 습 니 다.
#include 
int main(){
	int t,n,i,a,b,k;
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		k=1;
		for(i=2;i*i<=n;i++)
			if(n%i==0){k=i;break;}//   k 
		if(k==1)printf("1 %d
",n-1);// n else printf("%d %d
",n/k,n-n/k); } return 0; }

좋은 웹페이지 즐겨찾기