[C++] 백준 27856번: Sum of Remainders - Math

https://www.acmicpc.net/problem/27856

27856번: Sum of Remainders

 

자연수 n이 주어졌을 때,

1 ~ n까지의 정수를 배열 k의 원소로 나눈 나머지의 합이 Input으로 주어진다.

배열 k의 원소를 구하는 문제이다.

 

처음봤을 때는 아무 생각이 안들었는데,

손으로 써가면서 나머지를 구해보니 규칙이 보였다.

 

먼저  k의 원소는 2 이상이므로 자연수 1을 k의 원소로 나눈 나머지는 무조건 1이다.

그러므로 1에 대응하는 값은 원소 k의 개수가 된다.

 

다음 자연수 2를 보면,

나올 수 있는 나머지는 0, 2이다.

여기서 0이 되는 경우의 수는 2 % 2인 경우이고,

나머지가 1인 경우의 수는 없다.

나머지가 2인 경우의 수는 2를 넘어선 모든 정수이므로

해당 부분에서는 2의 개수를 구할 수 있다.

 

어떻게 구하냐면,

먼저 자연수 1에 대응하는 값이 원소의 총 개수이므로

해당 값을 p라고 하면,

만약 원소가 모두 2를 넘는 자연수라면 나머지가 모두 2가 되므로 입력 값은 2 * p가 되어야한다.

하지만 입력으로 주어진 수가 2 * p보다 작다면 2의 개수가 존재하는 것이고,

2 * p라면 2는 존재하지 않는다는 의미이다.

 

마찬가지로 자연수 3을 살펴보면 나올 수 있는 나머지는 0, 1, 3이다.

0은 3 % 3인 경우,

1은 원소에 2가 존재하는 경우 -> 이 경우는 앞선 과정에서 구했으므로 계산이 가능하다.

3은 원소가 3을 넘어선 자연수인 경우이다.

이번엔 3의 개수는 최대 p에서 2의 개수를 빼준 값이어야하므로

2의 개수를 l, 2가 아닌 원소의 개수를 p'이라고 하면 (p - 원소 2의 개수)

3 * p' + l * 2 == p * i 이어야한다.

이 역시 일치한다면 원소 3의 개수는 없는 것이고,

일치하지 않는다면 그만큼 3의 개수가 존재한다는 의미이다.

 

예제로 살펴보면,

16
4 6 10 12 6 8 12 14 18 10
3 5 9 11 5 7

 

1로 인해 원소 개수는 4개이고,

2번으로 인해 2의 개수는 1개 존재함을 알 수 있다.

어떻게 아냐면

2를 넘어선 원소로만 이루어져있으면 총 합은 8이어야하지만,

6인 것으로 보아 2가 1개 존재함을 알 수 있다.

3번은 10인데, 이는 2가 하나 존재하므로 일단 1이 확보되어있고 (3 % 2 == 1), 10 - 1인 9는

3 * 3이므로 3은 존재하지 않는다는 것을 알 수 있다.

 

#include <iostream>
#include <set>
using namespace std;
multiset<int>s;
int main(){
    int n, x, base, cnt; cin >> n;
    for(int i=1; i<=n; i++){
        cin >> x;
        if(i==1) base=x;
        else{
            cnt=0;
            for(auto it=s.begin(); it!=s.end(); it++) cnt+=i%(*it);
            cnt+=base*i;
            cnt-=x;
            cnt/=i;
            while(cnt--){
                s.insert(i);
                base--;
            }
        }
    }
    cout << s.size() << " ";
    for(auto e : s) cout << e << " ";
}