글 읽기 - 모듈러 연산 분배법칙(50점에서 벗어나고 싶습니다)

syl0390 2년 전 1

모듈러 연산에도 분배법칙이 있길래 참고해서 적용해봤는데도 왜 50점인지 모르겠습니다..

어디서 어떤 코드가 왜 잘못됬는지 알려주시면 감사하겠습니다.

분배법칙은 다음 링크를 참고했습니다

@gidskql6671/%EB%82%98%EB%A8%B8%EC%A7%80Modulo-%EC%97%B0%EC%82%B0-%EB%B6%84%EB%B0%B0%EB%B2%95%EC%B9%99">https://velog.io/@gidskql6671/...

#include <iostream>
#include <string>

#define M   1234567891


// mod == % 연산 == moduler operator


using namespace std;


int main(void) {
    int n;
    string key;

    cin >> n >> key;
    
    unsigned int convSum = 0;
    unsigned int r = 1;
    for(int i = 0; i < n; i++){
        int a = key[i] - 'a' + 1;
        int ar = (a * (r % M)) % M;
        convSum += ar;
        r *= 31 % M;
    }
    convSum %= M;

    cout << convSum;


    return 0;
}

limepencil 2년 전 2

일단 반례부터 드리자면

10
zzzzzzzzzz

답:76827671

출력:1146498867

25번이 문제로 보입니다. r의 모듈로 연산이 잘 되지 않는것 같습니다. r을 unsigned long으로 바꾸어주면 잘 작동합니다. 모둘러 연산을 진행해도 M이 int 범위와 근접하기 때문에 31을 곱하면 overflow가 나올수 있습니다.

limepencil 2년 전 1

마찬가지로 convsum도 넘어갈 수 있기 때문에 long으로 바꿔주시면 좋을것 같습니다

#include <iostream>
#include <string>

#define M   1234567891


// mod == % 연산 == moduler operator


using namespace std;


int main(void) {
    int n;
    string key;

    cin >> n >> key;
    
    unsigned long convSum = 0;
    unsigned long r = 1;
    for(int i = 0; i < n; i++){
        int a = key[i] - 'a' + 1;
        int ar = (a*r) % M;
        convSum += ar;
        r *= 31; 
        r%= M;
    }
    convSum %= M;

    cout << convSum;


    return 0;
}

syl0390 2년 전 0

정말 감사합니다ㅠㅠ 모듈러 연산 써서 overflow는 발생하지 않을 거라고 착각했는데 아니었네요..

덕분에 잘 해결했습니다!!

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

모듈러 연산 분배법칙(50점에서 벗어나고 싶습니다)

syl0390 2년 전 1

limepencil 2년 전 2

limepencil 2년 전 1

syl0390 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말