5615번: 아파트 임대 - 수학(밀러-라빈)

\(2xy + x + y = A\)라 하면, \(2A+1 = 2(2xy + x + y) + 1 = 4xy + 2x + 2y + 1 = (2x + 1)(2y+1)\)이다. \(x, y\)는 양수이기에 \(2x+1, 2y+1\)는 3 이상의 양수이고, 때문에 \(2A+1\)은 반드시 9 이상의 소수가 아닌 양수이다. 즉 \(2A+1\)에 대해 소수를 판별하면 문제를 해결할 수 있다.

 

단, 면적 \(A\)의 크기가 정수 최대 범위기에, \(O(sqrt(N))\) 소수판정법을 쓰면 TLE를 받는다. 때문에 \(O(log^3N)\) 소수 판정법인 밀러-라빈을 써야만 한다.

 

밀러-라빈을 쓸 때 지수로 들어가는 값이 정수 최대 범위이므로, long long이 아닌 unsigned long long을 써야 한다.

소수를 판정하는 범위가 정수 최대 범위이므로, \(a = 2, 3, 5, 7, 11\)까지만 확인해도 충분하다.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;

ull prime[5] = {2, 3, 5, 7, 11};

ull DnC(ull v, ull e, ull X)
{
    if(e == 0) return 1;
    
    ull b = DnC(v, e/2, X);
    if(e%2) return (b*b%X)*v%X;
    else return b*b%X;
}

bool solve()
{
    ull X; cin >> X;
    X = 2*X+1;
    
    if(X < 9) return true;
    
    for(int i=0; i<5; i++)
    {
        bool chk = false;
        
        ull d = X-1;
        while(true)
        {
            ull ret = DnC(prime[i], d, X);
            if(d % 2)
            {
                if(ret == X-1 || ret == 1) chk = true;
                break;
            }
            else if(ret == X-1) chk = true;
            d /= 2;
        }
        
        if(!chk) return false;
    }
    return true;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    
    int T; cin >> T;
    int ans = 0;
    while(T--) 
    {
        if(solve()) ans++;
    }
    cout << ans;
}