15711. 환상의 짝꿍

문제링크 : https://www.acmicpc.net/problem/15711

< 입력 >

테스트케이스 수(1<=T<=500)

2개의 끈의 길이 A,B (1<=A,B<=2*10^12)

< 출력 >

2개의 끈을 붙인 다음 정확히 2개의 소수로 나눌 수 있다면 YES, 아니면 NO

< 풀이 >

개인적으로 많은 이론을 안다고 자부할 수 있는 것도 아니고 문제를 보자마자 패턴을 떠올릴 자신이 없었다.

그래서 직접 A와 B의 합을 2부터 약 40까지 증가시키며 확인을 했다.

그렇게 진행하며 발견한 내용은 아래와 같다.

i) 4 이상의 짝수는 2개의 소수로 나눌 수 있다.

ii) 2를 제외한 모든 소수는 홀수이다.

   따라서 소수 + 2로 만들 수 없는 모든 홀수는 2개의 소수의 합으로 나눌 수 없다.

결국 4 이상의 짝수면 YES, 홀수면 -2한 값이 소수면 YES이고 나머지는 NO이다.

i)은 증명이 필요한 추측이지만 문제를 만드신 디디님의 블로그에서 이미 증명이 된 내용이라는 것을 알 수 있었다.

디디님 블로그 : https://blog.naver.com/rdd573/221270230610

이제 홀수에서 -2를 한 값이 소수인지 아닌지 구별만 하면 된다 !

근데 A와 B의 최대값이 2*10^12이다.

사실 진짜 문제는 이 부분이었다..

특정 수가 소수인지 O(logN)에 확인을 해야한다는 뜻이다.

그 부분에서 멘붕이 와서 방법을 찾아보던 중에 "밀러-라빈 소수판별법"이라는 방법을 발견했다.

내용을 정확하게 이해하지 못해서 설명은 https://casterian.net/archives/396 에서 보는걸로.. 헿

특정 수가 소수인지 O(logN)시간에 확인할 수 있는 방법이다.

이 방법은 확률론적 소수 판별법으로 "합성수이다."와 "아마도 소수일 것이다."라고 판별할 수 있다.

아마도라는 것은 예외가 있을 수 있다는 것이다.

하지만 2^32 이하의 경우 2,7,61 / 2^64 이하의 경우 2,325,9375,28178,450775,9780504,1795265022에

대해서만 밀러-라빈 소수판별법을 적용해봐도 예외가 발생하지 않게 된다.

정말 신기한 이론인데 이해하기 너무 어렵다.. 이해해봐야지 ㅜㅜ

---

- 소스 코드 -

import java.util.Scanner;
 
public class Main {
    static long primeTest[]= {2,325,9375,28178,450775,9780504,1795265022};
    public static void main(String[] args) {
        Scanner scan=new Scanner(System.in);
        int T=scan.nextInt();
        
        for(int test_case=1;test_case<=T;test_case++) {
            long A=scan.nextLong();
            long B=scan.nextLong();
            
            long sum=A+B;
            
            if(sum<4) {
                System.out.println("NO");
            }else if(sum%2==0) {
                System.out.println("YES");
            }else {
                sum-=2;
                if(is_prime(sum)) {System.out.println("YES");}
                else {System.out.println("NO");}
            }
        }
    }
    // calculate (x + y) % m; overflow-safe
    public static long addmod(long x, long y, long m) {
        x %= m;
        y %= m;
        return (x >= m - y? x - (m - y) : x + y);
    }
     
    // calculate (x * y) % m; overlow-safe
    public static long mulmod(long x, long y, long m) {
        x %= m;
        y %= m;
        long r = 0;
        while (y > 0) {
            if (y % 2 == 1)
                r = addmod(r, x, m);
            x = addmod(x, x, m);
            y /= 2;
        }
        return r;
    }
     
    // calculate x^y % m; overflow-safe
    public static long powmod(long x, long y, long m) {
        x %= m;
        long r = 1;
        while (y > 0) {
            if (y % 2 == 1)
                r = mulmod(r, x, m);
            x = mulmod(x, x, m);
            y /= 2;
        }
        return r;
    }
     
    // true for probable prime, false for composite
    public static boolean miller_rabin(long n, long a) {
        long d = n - 1;
        while (d % 2 == 0) {
            if (powmod(a, d, n) == n-1)
                return true;
            d /= 2;
        }
        long tmp = powmod(a, d, n);
        return tmp == n-1 || tmp == 1;
    }
     
    public static boolean is_prime(long n) {
        if (n <= 1)
            return false;
        if (n <= Long.parseLong("10000000000")) {
            for (long i = 2; i*i <= n; i++)
                if (n % i == 0)
                    return false;
            return true;
        }
        for (long a : primeTest)
            if (!miller_rabin(n, a))
                return false;
        return true;
    }
}
 

---