백준 2378 - 불필요한 수

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

 

문제에 주어진 N에서 일부 값에 대해 수열의 원소 $R_{i}$가 등장하는 횟수를 계산해 보면 이는 파스칼의 삼각형과 동일한 형태를 가짐을 파악할 수 있다.

 

그러면 길이가 N일 때 수열의 원소가 최종적으로 등장하는 횟수를 이항계수로 표현하면

 

$$Count(R) = \{ {N - 1 \choose 0}, {N - 1 \choose 1}, ..., {N - 1 \choose N - 1}  \}$$

 

으로 나타낼 수 있다.

 

그러면 N까지의 원소에서 이항계수를 구했을 때 나머지 M에 나눠떨어지는지 확인하면 되는데 $MAX(M) = 10^{9}$이고 M이 소수라는 조건이 없으므로 이를 처리하기 어려울 수 있다.

 

이를 처리하기 위해 양의 정수는 소인수의 곱으로 나타낼 수 있음을 이용하자.

 

그러면 $M = p_{1}^{a} \times p_{2}^{a} \times ...$으로 바꿀 수 있고 위 이항 계수들 역시 소인수의 곱으로 나타내어 M의 소인수 곱들에 나눠 떨어지는지 확인하는 것으로 모듈러 문제를 처리할 수 있다.

 

map 형태로 소인수 곱의 누적합을 계산하되, 모든 수에 대해 소인수 분해를 하면 시간 초과를 받을 수 있으므로 M의 소인수에 대해서만 계산하도록 하면 빠르게 확인이 가능하다.

 

정답 코드 - CPP

#pragma GCC target("avx,avx2,fma,bmi,bmi2,lzcnt,popcnt")
#pragma GCC optimize("O3,unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/pb_ds/assoc_container.hpp"
 
using namespace std;
using namespace __gnu_pbds;
 
using pii = pair<int, int>;
using ll = int_fast64_t;
 
ll n, m;
map<int, int> p_count;
map<int, int> pref[100001];
 
int spf[100001];
 
void sieve(int mx)
{
  for (int i = 2; i <= mx; i++)
  {
    if (spf[i]) continue;
    spf[i] = i;
    for (int j = i * 2; j <= mx; j += i)
    {
      spf[j] = i;
    }
  }
}
 
void solve()
{
  cin >> n >> m;
 
  if (n == 1)
  {
    cout << 0;
    return;
  }
 
  sieve(n);
 
  int mm = m;
  for (ll i = 2; i * i <= mm; i++)
  {
    while (mm % i == 0)
    {
      ++p_count[i];
      mm /= i;
    }
  }
 
  if (mm != 1)
  {
    ++p_count[mm];
  }
 
  pref[2][2] = 1;
  for (int i = 3; i <= n; i++)
  {
    int ii = i;
    pref[i] = pref[i - 1];
 
    while (spf[ii])
    {
      int x = spf[ii];
      
      if (p_count.count(x))
      {
        ++pref[i][x];
      }
      
      ii /= x;
    }
 
    if (ii != 1) ++pref[i][ii];
  }
 
  vector<int> ans;
 
  for (int i = 2; i < n; i++)
  {
    bool divided = true;
    auto mp = pref[n - 1];
 
    for (auto &[k, v] : pref[i - 1])
    {
      mp[k] -= v;
    }
 
    for (auto &[k, v] : pref[n - 1 - i + 1])
    {
      mp[k] -= v;
    }
 
    for (auto &[k, v] : p_count)
    {
      if (mp.count(k) == false or mp[k] < v)
      {
        divided = false;
        break;
      }
    }
 
    if (divided)
    {
      ans.push_back(i);
    }
  }
 
  cout << ans.size() << '\n';
  for (int i : ans) cout << i << ' ';
}
 
int main()
{
#ifdef LOCAL
//  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
#endif
 
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  solve();
}