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;
}