• 문제 : https://www.acmicpc.net/problem/4375

---

1. 문제 접근

• 마찬가지로 mod연산을 하면서 접근할 수 있다.

---

2. 시행착오

• 없음

---

3. 코드 및 풀이

3.1 풀이

mod 곱셈연산 : (A * B) mod C = (A mod C * B mod C) mod

• b가 홀수인 경우도 나타날 수 있다. (ex. a = 2, b = 7)
  • 그렇다면 재귀함수를 활용할 때, 2^7 = 2^3 + 2^4와 같은 경우가 생길 수 있음
  • 예외처리 하지 않으면 b는 long long 타입이므로 b/2 = 3이 나와서, 실제로는 2^3 * 2^3만 계산될 수밖에 없다.
  • 이를 처리하기 위해 2^3 * 2 = 2^4를, 즉 a를 한번 더 곱해줘야 한다.

처음 코드

#include <bits/stdc++.h>
using namespace std;

int n;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    while(cin >> n){
        int i = 1;
        long long ret = 1 % n;
        int mem = 1 % n;
        while(ret){
            mem = ( (10 % n) * mem ) % n;
            ret = (mem + ret) % n;
            i++;
        }
        
        cout << i << '\n';
    }
    return 0;
}

발전 코드

• 여기서 cnt = (cnt + 10 + 1)을 바로 해도 상관없게 된다.
• 원래 mod연산을 풀어쓰면, cnt = (cnt % n * 10 % n) + 1가 된다.
  • cnt % n은 0~n-1의 값을 가지게 되는데, 0~n-1의 값을 다시 %n해도 무조건 0~n-1의 동일한 값이 나오게 된다.
  • 따라서 cnt % n = cnt로 해도 상관없다.

#include <bits/stdc++.h>
using namespace std;

int n;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    while(cin >> n){
        int cnt = 1, ret = 1;

        while(cnt % n){
            cnt = (cnt * 10) + 1;
            cnt %= n;
            ret++;
        }
        
        cout << ret << '\n';
    }
    return 0;
}

---

Reference