취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 3870번 문제인 Find the Multiples이다.
문제는 아래 링크를 확인하자.

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

\(Q\)가 2 또는 5인 경우 각 자리수만 보고도 문제를 쉽게 해결할 수 있다. 그 외의 경우를 생각해 보자.

주어진 수의 임의의 substring으로 구성된 수는 0을 적절히 붙여 (해당 부분부터 끝까지 쓴 수에서 뒤에 덧붙인 수를 뺀 수)로 만들 수 있다. 한편, \(Q\)는 2나 5가 아니므로 10에는 \(Q\)의 소인수가 없고, 따라서 0을 뒤에 덧붙이거나 지워도 \(Q\)의 배수 여부는 변하지 않는다. 따라서 각 자리부터 시작하는 접미사의 형태로 이루어진 문자열의 집합을 이용해 문제를 해결할 수 있을 것임을 관찰할 수 있다.

문제 조건에 따라 0으로 시작하는 수는 고려하지 않는다는 점에 유의하자.

아래는 제출한 소스코드이다.

//3870
#include <iostream>
#include <algorithm>
#include <map>
using namespace std;
typedef long long ll;

ll N, S, W, Q, ans;
ll AA[100001];
ll A[100001];
map<int, int> mp;

void solve2() {
    int cnt0 = 0, cnt1 = 0;
    for (int i = 0; i < N; i++) {
        if (A[i] & 1) cnt1++;
        else {
            ans += cnt0 + cnt1;
            if (A[i]) cnt0++, ans++;
        }
    }
    cout << ans << '\n';
}

void solve5() {
    int cnt0 = 0, cnt1 = 0;
    for (int i = 0; i < N; i++) {
        if (A[i] % 5) cnt1++;
        else {
            ans += cnt0 + cnt1;
            if (A[i]) cnt0++, ans++;
        }
    }
    cout << ans << '\n';
}

void solve() {
    ans = 0;
    for (int i = 0; i < N; i++) {
        AA[i] = A[i] = (S / 7) % 10;
        if (S & 1) S = (S >> 1) ^ W;
        else S >>= 1;
    }

    //2와 5 예외처리
    if (Q == 2) {
        solve2();
        return;
    }
    else if (Q == 5) {
        solve5();
        return;
    }

    A[N] = 0;

    for (ll i = N - 1, d = 1; i > -1; i--, d = d * 10 % Q) {
        A[i] = (A[i + 1] + d * A[i]) % Q;
    }

    mp.clear();
    for (ll i = 0; i < N; i++) {
        ans += mp[A[i]];
        if (AA[i]) mp[A[i]]++;
    }
    ans += mp[0];
    
    cout << ans << '\n';
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> S >> W >> Q;
    while (N) solve(), cin >> N >> S >> W >> Q;
}