백준 10986 - 나머지 합

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

힌트

$(A - B) \mod m = (A \mod m) - (B \mod m)$

풀이

나머지의 성질에 대해 생각하면

 

$(A - B) \mod m = (A \mod m) - (B \mod m)$ 가 성립됨을 알 수 있을 것이다.

 

이를 문제에 적용하면 모듈러 값이 같다는 건 둘을 뺐을 때 0이 된다는 소리고 즉, pref[A] - pref[B]가 m으로 나누어진다는 것이 된다.

 

따라서 우리는 누적합을 계산하면서 각 나머지의 횟수를 세주고 $\binom{N}{2}$ 을 모두 계산해주면 된다.

 

참고로 나머지가 0인 경우는 이미 나누어진 것이므로 이거는 따로 더해주도록 한다. 물론 이항 계수의 계산에도 포함해야 한다.

 

전체 코드

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/rope"
 
using namespace std;
using namespace __gnu_cxx;
 
using ll = long long;
using pii = pair<int, int>;
 
int n, m;
ll pref[1000001];
int mods[1000];
 
void solve()
{
  cin >> n >> m;
  for (int i = 1; i <= n; i++)
  {
    cin >> pref[i];
    pref[i] += pref[i - 1];
  }
 
  ll cnt = 0;
  for (int i = 1; i <= n; i++)
  {
    mods[pref[i] % m]++;
  }
 
  cnt = mods[0];
  for (int i = 0; i < m; i++)
  {
    if (mods[i]) cnt += (ll)mods[i] * (mods[i] - 1) / 2;
  }
  cout << cnt;
}
 
int main()
{
#ifdef LOCAL
  freopen("input.txt", "r", stdin);
//  freopen("output.txt", "w", stdout);
#endif
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

제출 기록