InterestingDigits

문제

base 진법이 주어졌을때, 이러한 성질을 가진 수를 오름차순으로 출력한다.

10진수

12는 3의 배수
3x4 = 12

1+2 도 3의 배수

{3}

81은 9의 배수

8+1 도 9의 배수

{3,9}

예시 입력

10
3
9
26
30

예시 출력

3 9
2
2 4 8
5 25
29

생각의 변화

10진수는 [0..9], 16진수는 [0..f], 30진수는 [0..t]

m의 배수의 각 자리숫자를 더하면 m의 배수가 되는 성질을 조건식으로 적어본다

q = (i x j) / n
r = (i x j) % n 을 고민해보았으나 '자리수 개념' 이 필요했다

숫자가 4자리 미만으로 제시되어 있으므로 ij 루프 대신 ijk 루프를 사용해 각 자리를 표현한다

m의 배수라는 조건은 다음과 같이 표현된다
{(i+j+k)/n != 0} && {(i+k+k)%n == 0}

000 이나 00m 인 경우에 대한 예외처리

계속 검토해야 한다. [0..999]
검토해서 한번도 m의 배수 조건이 깨지지 않았으면 m 을 ans 에 넣는다

m의 배수인 수가 있고
이 수의 각 자리숫자를 더하는 것이므로, 모든 수에 대해 하진 않아도 된다

pseudo code

digits(base)
    vector<int> ans
    
    for  m=2  m<base  m++
        bool loop_stop = false;
        
        for  i=0  i<base && !loop_stop  i++
            for  j=0  j<base && !loop_stop  j++
                for  k=0  k<base && !loop_stop  k++
                
                    if i==0 && j==0 && (k==m || k==0)
                        continue
                    
                    if ((i*base*base + j*base + k) % m) == 0
                        if ((i+j+k) / m) != 0 && ((i+j+k) % m) == 0
                        else
                            loop_stop = true
        if  !loop_stop
            ans.push_back(m)

    return ans