백준 4233 가짜소수 C++

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

4233번: 가짜소수

---

정말 정말 많이도 풀었다...

정말 많이 풀었다..22

---

문제

페르마의 소정리 (Fermat's little theorem)의 내용은 다음과 같다.

p가 소수일 때, 임의의 정수 a>1에 대해서, a^p == a (mod p)가 성립한다.

즉, a를 p제곱한 뒤, p로 나눴을 때, 나머지는 a가 되는 것이다.

하지만, p가 소수가 아닌 경우에 어떤 정수 a에 대해서 위의 식을 만족하는 경우가 있다. 이때, p를 밑이 a인 가짜소수라고 한다. (모든 a에 대해서 식을 만족하는 수를 카마이클 수라고 한다)

p와 a가 주어졌을 때, p가 밑이 a인 가짜소수인지 아닌지 알아내는 프로그램을 작성하시오. 

---

입력

입력은 여러 개의 테스트 케이스로 이루어져 있다. 각 테스트 케이스는 한 줄로 이루어져 있고, p와 a를 포함하고 있다. 입력의 마지막 줄에는 "0 0"이 주어진다. (2 < p ≤ 1,000,000,000, 1 < a < p)

---

출력

각 테스트 케이스에 대해서, p가 밑이 a인 가짜소수라면 yes를, 아니라면 no를 한 줄에 하나씩 출력한다.

---

이 문제도 전에 포스팅 한, 거듭제곱에 관한 문제이다.

일단 p와 a가 주어지는데, p가 소수일 떄, 임의의 정수 a>1에 대해서 a^p  == a(mod p)가 성립할 수 있다.

즉, a를 p제곱한뒤 p로 나눴을때 나머지는 a가 되는 것이다. 

하지만 p가 소수가 아닐떄, 어떤 a에 대해서 위의 식을 만족시키면 p를 밑이 a인 가짜소수라고 한다.

 

p와 a가 주어졌을 떄 p가 밑이 a인 가짜소수인지 알아내야 하는 것이 목적이다.

일단 a와 p를 입력받고 a와 p를 결정해야 하는데, p가 항상 a보다 크므로 (1 < a < p)

큰 값을 p에 작은 값을 a에 담는다. (a와 p가 모두 0이면 프로그램 종료)

       //ll은 long long
       
       ll a,p;
        cin >> p >> a;
        
        if(a == 0 && p == 0){
            return 0;
        }
        p = max(a,p);
        a = min(a,p);

 

p가 소수가 아닐 떄 가짜소수이니깐, p가 소수면 가짜소수가 성립 안한다. 그래서 p가 소수인지 아닌지

판별하는 함수를 만들었다.

 

p가 소수라면 no를 출력하고 p가 소수가 아닐 떄 , 다시 판별을 할텐데, 일단 p가 소수인지 아닌지 판별하는 함수는 다음과 같다. 소수라면 1을 리턴한다. 소수가 아니면 -1을 리턴해서 소수인지 판별을 해준다.

ll check_prime(ll num){ 
    //소수 최적화(루트 num까지 확인) 
    
    for(int i = 2;i*i <= num;i++){
        if(num%i == 0){
            return -1;
        }
    }
    return 1;
}

 

 그리고 p가 소수가 아니면 밑이 a인 가짜소수인지 판별하는데, 전에 쓴 글과 같은 논리의 함수이다.(괄호를 꼭 적절히..)

그리고 계산 과정마다 mod연산을 해주었다.

ll dfs(ll a,ll p){
    if(p == 0){
        return 1;
    }
    else if(p == 1){
        return a;
    }
    else if(p%2 == 0){
        return (dfs(a,p/2) % mod * dfs(a,p/2) % mod) % mod;
    }
    else if(p%2 != 0){
        return (a * dfs(a,p-1) % mod) % mod;
    }
}

 

전체 소스코드 ->

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

//A^P % P == A (P가 소수가 아니면 가짜소수)
ll mod;

ll max(ll a,ll b){
    if(a>b){
        return a;
    }
    else{
        return b;
    }
    
}

ll min(ll a,ll b){
    if(a>b){
        return b;
    }
    else{
        return a;
    }
    
}

ll check_prime(ll num){ 
    //소수 최적화(루트 num까지 확인) 
    
    for(int i = 2;i*i <= num;i++){
        if(num%i == 0){
            return -1;
        }
    }
    return 1;
}

ll dfs(ll a,ll p){
    if(p == 0){
        return 1;
    }
    else if(p == 1){
        return a;
    }
    else if(p%2 == 0){
        return (dfs(a,p/2) % mod * dfs(a,p/2) % mod) % mod;
    }
    else if(p%2 != 0){
        return (a * dfs(a,p-1) % mod) % mod;
    }
}



int main(void){
    while(1){
        ll a,p;
        cin >> p >> a;
        
        if(a == 0 && p == 0){
            return 0;
        }
        p = max(a,p);
        a = min(a,p);
        
        mod = p;
        ll check_ = check_prime(p);
        if(check_== 1){
            cout << "no" << '\n';
            continue;
        }
        
       if(dfs(a,p) == a){
           cout << "yes" << '\n';
       }
        else{
            cout << "no" << '\n';
        }

    }
}