백준 4233번: 가짜소수 (C++)

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

4233번: 가짜소수

---

Solved By: Exponentiation By Squaring, Primality Test

 

페르마의 소정리 개념을 공부하려다가 풀게 된 문제입니다.

 

입력값으로 p와 a가 들어오면 a ^ p를 구하고 p로 나누었을 때, a인지 판정 후에 나누었던 p가 소수인지 아닌지를 판정하면 끝나는 문제입니다.

다만, int형의 오버플로우, 분할 정복을 이용한 거듭제곱, Modular의 분배 법칙, 소수 판정 방법을 알아야 문제를 풀 수 있습니다.

 

int 형의 오버플로우를 해결하기 위해서는 long long 타입으로 변수들을 선언하여 풀었고,

a^p에서 p의 숫자가 큰 수가 나올 수도 있어서 이를 빠른 시간 안에 해결하기 위해 분할 정복을 이용한 거듭제곱을 사용했습니다.

거듭제곱을 하는 과정에서 오버플로우가 나올 수도 있기 때문에 Modular 분배 법칙을 활용하여 리턴하는 value 값에 p를 Modular 연산해주었습니다.

그리고, 소수 판정 방식에 있어서는 2부터 root N까지만 확인을 하여 약수가 없는 경우를 소수로 판정하여 더 빠르게 리턴하도록 해주었습니다. 

#include <iostream>
#include <vector>
#include <cmath>
#define ll long long
using namespace std;

ll mod;

ll POW(ll a, ll b){
    if(b == 0) return 1;
    else if(b == 1) return a;
    
    ll value = POW(a, b / 2) % mod;
    
    if(b % 2){
        return (((value * value) % mod) * (a % mod)) % mod;
    }
    else{
        return (value * value) % mod;
    }
}

bool isPrime(ll n){
    for(int i = 2; i <= sqrtl(n); i++){
        if(n % i == 0) return false;
    }
    return true;
}

int main(){
    vector<string> ans;
    while(true){
        ll p, a; cin >> p >> a;
        if(p == 0 && a == 0) break;
        
        mod = p;
        
        if((POW(a, p) % p) == a){
            // p가 가짜 소수인지 아닌지 판정
            if(isPrime(p)) ans.push_back("no");
            else ans.push_back("yes");
        }
        else ans.push_back("no");
    }
    
    for(int i = 0; i < ans.size(); i++){
        cout << ans[i] << '\n';
    }
    
    return 0;
}