1009 분산처리

BOJ::1009 분산처리

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

풀이 : 

이문제의 핵심은 0~9까지 숫자들이 제곱할때 생기는 1의자리 숫자의 순환주기를 구하는것이다.

예를들어

2 - 4 - 8 - 16 - 32 : 순환주기 4

3 - 9 - 27 - 81 - 273 : 순환주기 4

4 - 16 - 64 : 순환주기 2

이를 이용하면 답을 쉽게 구할 수 있다.

C++

#include <iostream>
#include <math.h>
using namespace std;
 
int getCircle(int a) {
    if (a == 1 || a == 0) {
        return 1;
    }
 
    bool *check=new bool[10];
    for (int i = 0; i < 10; i++) {
        check[i] = false;
    }
 
    int v = a;
    int cnt = 0;
    while (!check[a]) {
        cnt++;
        check[a] = true;
        a = (a * v)%10;
    }
    delete[] check;
    return cnt;
}
 
int pow(int a, int b) {
    int v = a;
    for (int i = 0; i < b - 1; i++) {
        a *= v;
    }
    return a;
}
 
int main() {
    int n;
    //circleArray에 순환주기를 저장
    int circleArray[10];
    for (int i = 0; i < 10; i++) {
        circleArray[i] = getCircle(i);
    }
 
    cin >> n;
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        a = a % 10;
 
        if (a==0) {
            cout << 10 << endl;
        }
        else if (a == 1 || a == 6) {
            cout << a << endl;
        }
        else {
            while (b > circleArray[a]) {
                b -= circleArray[a];
            }
            a = pow(a, b)%10;
            cout << a << endl;
        }
    }
}

JAVA

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
class Main{
    
    public static void main(String args[]) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //순환주기를 담을 배열
        int circleArray[] = new int[10];
        for(int i = 0 ; i <=9;i++){
            circleArray[i]=getCircle(i);
        }
        
        int n = Integer.parseInt(br.readLine());
        for(int i = 0 ; i < n ; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            a=a%10;
            if(a==0){
                System.out.println(10);
            }
            else if(circleArray[a]==1){
                System.out.println(a);
            }else{
                while(b>circleArray[a]){
                    b-=circleArray[a];
                }
                System.out.println(pow(a,b)%10);
            }
        }
    }
    
    //제곱하기
    public static int pow(int a, int b){
        int v = a;
        for(int i = 0 ; i < b-1 ; i++){
            a=a*v;
        }
        return a;
    }
    
    //순환 주기구하기
    public static int getCircle(int a){
        if(a==0 || a==1){
            return 1;
        }
        int cnt=0;
        int v=a;
        boolean[] check=new boolean[10];
        while(!check[a]){
            cnt++;
            check[a]=true;
            a=(a*v)%10;
        }
        return cnt;
    }
}