Codeforces Round 713 (Div. 3)

Dashboard - Codeforces Round 713 (Div. 3) - Codeforces

 

A

배열을 정렬하면 구하려는 수는 처음이나 끝에 위치하게 된다.

 

C

아래 코드의 주석 순서로 greedy 알고리즘을 진행하면 된다.

 

E

1부터 n까지의 자연수 중, 서로 다른 수 k개의 합의 범위를 생각해보자.
하한은 1 + 2 + ... + k 이고 상한은 n+ (n-1) + ... + (n-k+1) 이다.

이제 1부터 5까지의 자연수 중 합이 10인 서로 다른 수 3개의 수를 만들어보자.
10이 하한(1+2+3=6)과 상한(3+4+5=12) 사이의 수 이므로 가능하다.

하한이 되는 경우에서 부족한 값을 더해서 만들자.
1 2 3

합이 10이 되기 위해서는 4만큼이 부족하다. 따라서 위 배열에 4를 적절히 분해해야한다.
1 1 2 를 각 원소에 더해주면 조건을 만족하는 수
2 3 5 
를 만들 수 있다.

이때 까다로운 것은  부족한 수를 어떻게 분배해야 하는지이다. 몇 가지 예시에 위와 동일한 논리를 적용하여 규칙성을 찾아보자.

i) 위와 동일한 조건에서 합이 12인 경우를 만들어보자.
하한 [ 1 2 3 ] 에서 6만큼이 부족하므로 [ 2 2 2 ] 로 분배하면 된다.

ii) 위와 동일한 조건에서 합이 11인 경우를 만들어보자.
하한 [ 1 2 3 ] 에서 5만큼이 부족하므로 [ 1 2 2 ] 로 분배하면 된다.

iii) 위와 동일한 조건에서 합이 10인 경우를 만들어보자.
하한 [ 1 2 3 ] 에서 4만큼이 부족하므로 [ 1 1 2 ] 로 분배하면 된다.

iv) 위와 동일한 조건에서 합이 9인 경우를 만들어보자.
하한 [ 1 2 3 ] 에서 3만큼이 부족하므로 [ 1 1 1 ] 로 분배하면 된다.

v) 위와 동일한 조건에서 합이 8인 경우를 만들어보자.
하한 [ 1 2 3 ] 에서 2만큼이 부족하므로 [ 0 1 1 ] 로 분배하면 된다.

규칙)
req 만큼 필요하다고 하자. q = req//3, r = req%3일때, 먼저 모든 수에 q만큼 수를 더해주고
오른쪽 수부터 r개에 1씩 더해주면 된다.

 

 

G

multiplicative(곱셈함수) 문제는 대부분 seive 문제이다

방법 1 - Eratosthenes seive

 

방법 2 - Linear seive

 

#include <bits/stdc++.h>
#define endl '\n' // don't use when you cover interactive problem
#define all(v) v.begin(), v.end()
 
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
 
const ll MAX = 1e7;
// pr[i] := i'th prime
// cnt[i] := the power of the smallest prime factor of i
// d[i] := the sum of all divisors of the number i
vector<ll> pr, cnt, d;
vector<bool> is_composite;
 
// return a^b
ll binary_pow(ll a, ll b)
{
    ll ret = 1;
    ll base = a;
    while(b > 0){
        if(b&1) ret *= base;
 
        b >>= 1;
        base *= base;
    }
    return ret;
}
 
// return d[a^b] where a is prime
// d[a^b] = 1 + a + a^2 + ... + a^b = (a^(b+1)-1)/(a-1)
int f(ll a, ll b)
{
    return (binary_pow(a, b+1)-1)/(a-1);
}
 
int main() {
    ios::sync_with_stdio(false), cin.tie(0);
 
    is_composite.assign(MAX, false);
    cnt.assign(MAX+1, 0);
    d.assign(MAX+1, 0);
    d[1] = 1;
    for(ll i = 2; i <= MAX; ++i){
        if(!is_composite[i]) {
            pr.emplace_back(i);
            // i의 최소 소인수(i 그 자체)의 개수는 1.
            cnt[i] = 1; 
            // 자연수 i의 약수의 합은 i+1.
            d[i] = i+1;
        }
        
        // 소수가 작은것부터 큰 순으로 순회함
        // p = 2, 3, 5, 7 ...
        for(auto p: pr){
            if(i*p > MAX) break;
            // i*p의 최소 소인수가 p일때까지 loop를 반복한다.
            // 즉, (i의 최소 소인수) <= p 이면 loop를 반복한다.
 
            // i*p의 최소 소인수가 p이므로 i*p는 합성수이다.
            is_composite[i*p] = true;
 
            // p|i 이면 i*p의 최소 소인수가 p인 마지막 순간이다.
            // p보다 더 큰 소수 p' 이상부터는 i*p'의 최소 소인수가 p'가 아니다
            if (i%p == 0){
                // (remind) i의 최소 소인수가 pr[i].
                // i*pr[j]의 최소 소인수(pr[j])의 개수는 i에서 pr[j]의 개수에 1을 더해주면 된다.
                cnt[i*p] = cnt[i] + 1;
                // d가 multiplicative function 이므로 정의를 이용하자.
                // d[ab] = d[a]d[b] if (a, b) == 1
                // d[i*p] = d[i/p^cnt[i]]*d[p^(cnt[i]+1)];
                d[i*p] = d[i/binary_pow(p, cnt[i])]*f(p, cnt[i]+1);
                break;
            }
            else {
                cnt[i*p] = 1;
                d[i*p] = d[i]*d[p];
            }
        }
    }
 
    vector<ll> ans(MAX+1, -1);
    for(ll i = MAX; i >= 1; --i){
        if(d[i] <= MAX) ans[d[i]] = i;
    }
 
    ll T; cin >> T;
    while(T--){
        ll x; cin >> x; 
        cout << ans[x] << endl;
    }
 
    return 0;
}cs

linear seive 참고

Linear Sieve - Algorithms for Competitive Programming

 

[Tutorial] Math note — linear sieve - Codeforces