Codeforces Round #729 (Div. 2) ABC 풀이

A. Odd Set

 

문제 설명 + 풀이

 

2n 개의 숫자가 주어진다. 이 수들 중 두 개씩 골라 n개의 페어를 만들고, 이 페어 안에 있는 두 수의 합이 모두 홀수가 될 수 있는지 확인하는 문제입니다.

 

간단합니다. 두 수의 합이 홀수가 되기 위해서는 반드시 홀수 + 짝수로 구성되어야 합니다.

따라서 2n개의 수들 중 n개가 홀수, n개가 짝수라면 yes, 아니면 모두 no입니다.

 

소스 코드(. cpp)

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t; cin >> t;
	while (t--) {
		int n; cin >> n;
		int odd = 0, even = 0;
		for (int i = 0; i < 2 * n; i++) {
			int tmp; cin >> tmp;
			if (tmp % 2 == 0) even++;
			else odd++;
		}
		if (even == odd) cout << "Yes\n";
		else cout << "No\n";
	}
}

 

 

B. Plus and Multiply

 

문제 설명 + 풀이

 

다음을 만족하는 무한 집합이 있습니다.

• 1이 포함됩니다.
• 만약 x가 이 집합에 있다면, x*a, x+b 도 이 집합 안에 있습니다.

 

a, b, n이 주어질 때, n이 이 집합 안에 포함될 수 있으면 yes, 아닌 경우 no를 출력합니다.

 

이 문제의 경우 a, b, n 이 최대 10억이고, 테스트 케이스도 10만이므로 각 쿼리마다 O(logn)으로 해결하는 게 정답이라고 추측할 수 있습니다. 따라서 일단 규칙을 찾기 위해 직접 가지치기해봅시다.

 

 

곰곰이 생각해보면 같은 행의 공통된 특징은, (1, a, a^2, a^3,...)을 빼면 모두 b로 나누어 떨어진다는 점입니다.

이 점을 이용하면, 1부터 n보다 작은 a^x까지 빼면서 b로 나누어 떨어지는지 확인하면 됩니다.

이 경우 a=1을 따로 예외 처리한다면, 최대 시간 복잡도는 logn 이 됩니다. (a가 2인 경우)

 

 

소스 코드(.cpp)

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t; cin >> t;
	while (t--)
	{
		ll n, a, b;
		cin >> n >> a >> b;
 
		if (a == 1) {
			if ((n-1) % b == 0) cout << "Yes\n";
			else cout << "No\n";
		}
		else {
			ll tmp = 1;
			bool flag = false;
			while (tmp <= n) {
				if ((n - tmp) % b == 0) {
					flag = true;
					break;
				}
				tmp *= a;
			}
			if (flag) cout << "Yes\n";
			else cout << "No\n";
		}
	}
}

 

C. Strange Function

 

문제 설명 + 풀이

 

f(i)는 i의 약수가 아닌 수들 중 최솟값이라고 합니다.

n이 주어졌을 때 f(1) +... + f(n)을 구하면 됩니다.

---

 

우선 n이 최대 10^16 이므로, 배열에 저장한다거나(메모리 초과) 완전탐색한다거나(시간 초과) 할 수 없습니다.

b번과 마찬가지로 규칙을 찾아야 합니다.

 

• f(1) = 2, f(2) = 3
• f(3) = 2, f(4) = 3
• f(5) = 2, f(6) = 4
• f(7) = 2, f(8) = 3
• f(9) = 2, f(10) = 3

이 정도만 보면, 우선 홀수는 2를 약수로 갖지 않기 때문에 무조건 2가 됩니다.

또한 6은 특별하게도, 10 이하 수들 중 2, 3을 동시에 약수로 가지고 있어 4가 됩니다.

 

그럼 2*3 = 6의 배수들은 모두 2, 3을 동시에 약수로 가지므로 최소 4 이상의 값을 가진다는 사실을 알 수 있습니다.

 

그럼 다음은 2*3*4 = 24의 배수들은 모두 최소 5일까요?

이 질문은 반은 맞고 반은 틀렸습니다.

 

24, 48, 72 등 24의 배수는 모두 5 이상은 맞지만, 24보다 작은 12도 1~4까지 약수로 가지므로 5가 될 수 있습니다.

그 이유는 12를 소인수 분해하면 찾을 수 있는데, 12 = 1 * 3 * 2 * 2로 2가 두 개라서 2, 4 모두 약수입니다.

따라서 12의 배수는 모두 최소 5 이상이라고 해야 합니다.

 

이렇게 기준이 되는 수들은 최소 공배수의 특징을 이용하면 됩니다.

 

최소 i 이상 기준 수 = i-1 이상 기준 수와 i-1의 최소 공배수

 

12 = 6과 4의 최소 공배수

60 = 12와 5의 최소 공배수

60 = 12와 6의 최소 공배수

420 = 60과 7의 최소 공배수

...

 

이런 식으로 구해두면 답 찾는 건 간단합니다.

 

만약 n이 주어졌을 때,

2의 배수가 아닌 수들은 모두 2이고, 총 n / 2 개입니다.  --> 정답에 2 * 해당 개수만큼 추가

6의 배수가 아닌 수들은 모두 3이고, 총 (남은 수 - n / 6) 개입니다. --> 정답에 3 * 해당 개수만큼 추가

12의 배수가 아닌 수들은 모두 4이고, 총 (남은 수 - n / 12) 개입니다. --> 정답에 4 * 해당 개수만큼 추가

...

계속 구한 최소 공배수가 n이 넘어가면 더 이상 구할 필요가 없으니 계산을 종료합니다.

 

생각보다 소수가 많아서 몇 개 안돼서 모두 계산이 끝나버립니다.

 

 

 

소스 코드(.cpp)

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
 
const ll mod = 1000000007;
 
ll gcd(ll a, ll b) {
	return b ? gcd(b, a % b) : a;
}
ll find_lcm(ll a, ll b) {
	return a * b / gcd(a, b);
}
int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int t; cin >> t;
	while (t--) {
		ll n; cin >> n;
		ll remain = n;
 
		ll ans = 0;
 
		ll lcm = 1;
		for (ll i = 2; i < 100; i++) {
			lcm = find_lcm(lcm, i);
			if (lcm > n) {
				ans = (ans + remain * i) % mod;
				break;
			}
 
			ans = (ans + (remain - (n / lcm)) * i) % mod;
			remain = (n / lcm);
		}
		cout << ans << "\n";
	}
 
	return 0;
}