[SWEA] 7193 : 승현이의 수학공부

https://swexpertacademy.com/main/code/problem/problemDetail.do?problemLevel=3&contestProbId=AWksRkI6AR0DFAVE&categoryId=AWksRkI6AR0DFAVE&categoryType=CODE&problemTitle=&orderBy=RECOMMEND_COUNT&selectCodeLang=JAVA&select-1=3&pageSize=10&pageIndex=4 

SW Expert Academy

N의 범위가 너무 커서 어떻게 풀어야 하는 건지 감이 안왔다.

이 정도로 큰 수면 계산이 아니라 어떤 규칙을 찾는 것일 텐데 그 규칙을 찾을 수가 없어서 고민하다가 다른 사람의 풀이를 찾아보았음.

 

페르마의 소정리라는데... 지수가 소수가 아닌데 페르마의 소정리가 왜 적용되는지는 납득이 안갔다.

일단 규칙은 제공된 테스트케이스를 예시로 들면

1 ) 9진법 234를 8로 나누었을 때 나머지가 1 == 2 + 3 + 4를 8로 나누었을 때 나머지가 1

2 ) 5진법 123을 4로 나누었을 때 나머지가 2 == 1 + 2 + 3을 4로 나누었을 때 나머지가 2

3 ) 3진법 102를 2로 나누었을 때 나머지가 1 == 1 + 0 + 2를 2로 나누었을 때 나머지가 1

이렇게 볼 수 있다.

 

이 규칙을 뒷받침하는 개념이 페르마의 소정리라는데 납득이 안가서 다른 풀이로 풀어보겠다.

N진법으로 표현된 수를 (N - 1)로 나누면 각 자릿수마다 자릿수의 값만큼 나머지가 생긴다.

예를 들어 N 을 (N - 1)로 나누면 1이 남기 때문에 N^1000을 (N - 1)로 나눈 나머지도 1^1000 즉 1이고, 이렇게 아무리 지수가 커도 나머지는 1로 동일해서 자릿수의 값만큼이 나머지로 되기 때문임.

('/'가 아니라 '%'를 사용하는 것이기 때문에 가능)

9진법의 234은 2 * 9^2 + 3 * 9 + 4이고 이를 8로 나눈 나머지는 각 자릿수의 나머지 값들의 합 2 * 1 + 3 * 1 + 4를 8로 나눈 나머지의 값이 답이다.

 

내 코드

메모리 : 138244 KB

코드 : 503 ms

코드길이 : 775 B

 

[내 코드]

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Solution {

	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st;
		
		int T = Integer.parseInt(br.readLine());
		for(int t = 1; t <= T; t++) {
			sb.append('#').append(t).append(' ');
			st = new StringTokenizer(br.readLine());
			int N = Integer.parseInt(st.nextToken());
			String X = st.nextToken();
			
			long number = 0;
			for(int i = 0; i < X.length(); i++) {
				number += (X.charAt(i) - '0');
			}
			sb.append(number % (N - 1)).append('\n');
		}
		System.out.print(sb);
	}

}