백준 17633번: 제곱수의 합 (More Huge) (C++)

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

17633번: 제곱수의 합 (More Huge)

---

Solved By: Pollard's Rho, Number Theory

 

이번 문제는 기존에 가지고 있던 수학 지식으로는 풀 수 없었습니다. 그래서 공부를 한 뒤 풀어야 했습니다.

• Fermat's Two-Square Theorem
• Legendre's Three-Square Theorem
• Lagrange's Four-Square Theorem

 

본격적으로 문제에 들어가기 전에 문제를 읽어보면 라그랑주는 이미 자연수가 4개의 제곱 수의 합 이하로 나타낼 수 있다고 정리했습니다. 즉, 이번 문제에서는 N이 1, 2, 3개의 제곱수의 합으로 표현되는지만 살펴보면 됩니다.

 

[One-Square Check]

N이 하나의 제곱수로 이루어지는지 확인하는 제일 간단한 방법은 sqrt() 함수를 쓰는 것입니다. 하지만, int의 범위를 넘어가기 때문에 N의 소인수들이 각각 짝수개씩 있는지 확인하면 됩니다.

bool check1(){
    if(factors.size() % 2) return false;
    for(int i = 0; i < factors.size(); i += 2){
        if(factors[i] != factors[i + 1]) return false;
    }
    return true;
}

 

[Fermat's Two-Square Theorem]

N의 소인수 p가 있다고 가정했을 때, 이 p가 4k + 3 꼴이고, 짝수개만큼 있다면 N은 2개의 제곱수의 합으로 나타낼 수 있습니다.

(단, 4k + 3 꼴의 p가 모두 짝수개여야 합니다.)

bool check2(){
    bool flag = true;
    int exp_cnt = 1;
    for(int i = 1; i < factors.size(); i++){
        if(factors[i] == factors[i - 1]) exp_cnt++;
        else{
            if(factors[i - 1] % 4 == 3 && exp_cnt % 2 != 0) flag = false;
            exp_cnt = 1;
        }
    }
    if(factors[factors.size() - 1] % 4 == 3 && exp_cnt % 2 != 0) flag = false;
    return flag;
}

 

[Legendre's Three-Square Theorem]

N이 4^x * (8k + 7) 꼴이 아니라면 N을 3개의 제곱수의 합의 형태로 나타낼 수 있습니다.

bool check3(ull n){
    while(n % 4 == 0) n /= 4;
    if(n % 8 != 7) return true;
    else return false;
}

 

[Lagrange's Four-Square Theorem]

여기선 방법이랄 게 없습니다. 이미 문제에서 라그랑주는 모든 자연수는 4개의 제곱수의 합 이하로 나타난다 정리하였기 때문에 위의 3가지를 모두 통과하지 않는다면 해당 N은 4개의 제곱수의 합으로 이루어진다고 하면 되겠습니다.

 

---

소인수 분해를 하는 방법은 Pollard's Rho를 사용하여 풀었습니다.

#include <iostream>
#include <vector>
#include <algorithm>
#define i128 __int128
#define ull unsigned long long
using namespace std;

vector<ull> factors;

ull power(i128 a, i128 b, i128 mod){ // 피연산자 또한 같은 자료형이어야 overflow가 안 남
    a %= mod;
    i128 ret = 1; // overflow 방지
    while(b > 0){
        if(b % 2 == 1) ret = (ret * a) % mod;
        a = (a * a) % mod;
        b /= 2;
    }
    return (ull)ret;
}

bool millerRabin(ull n, ull a){
    if(a % n == 0) return true;
    ull k = n - 1;
    while(true){
        ull temp = power(a, k, n);
        if(temp == n - 1) return true;
        if(k % 2) return (temp == 1 || temp == n - 1);
        k /= 2;
    }
    
}

bool isPrime(ull n){
    if(n == 1) return false;
    else if(n == 2) return true;
    else if(n % 2 == 0) return false;
    else{
        ull base[12] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
        for(auto a : base){
            if(n == a) return true;
            if(!millerRabin(n, a)) return false;
        }
        return true;
    }
}

i128 f(i128 x, i128 c, i128 mod){
    return ((x * x) % mod + c) % mod;
}

i128 gcd(i128 a, i128 b){
    while(true){
        i128 temp = a % b;
        a = b;
        b = temp;
        if(b == 0) return a;
    }
}

i128 abs128(i128 x){
    if(x < 0) return -x;
    else return x;
}

void factorize(i128 n){
    if(n == 1) return;
    else if(n % 2 == 0){
        factors.push_back(2);
        factorize(n / 2);
        return;
    }
    else if(isPrime(n)){
        factors.push_back(n);
        return;
    }
    else{
        i128 x, y, c, g = n;
        do{
            if(g == n){
                x = y = rand() % (n - 2) + 2;
                c = rand() % 10 + 1;
            }
            x = ((x * x) % n + c) % n;
            y = ((y * y) % n + c) % n;
            y = ((y * y) % n + c) % n;
            g = gcd(abs128(x - y), n);
        } while(g == 1);
        
        factorize(g);
        factorize(n / g);
    }
}

bool check1(){
    if(factors.size() % 2) return false;
    for(int i = 0; i < factors.size(); i += 2){
        if(factors[i] != factors[i + 1]) return false;
    }
    return true;
}

bool check2(){
    bool flag = true;
    int exp_cnt = 1;
    for(int i = 1; i < factors.size(); i++){
        if(factors[i] == factors[i - 1]) exp_cnt++;
        else{
            if(factors[i - 1] % 4 == 3 && exp_cnt % 2 != 0) flag = false;
            exp_cnt = 1;
        }
    }
    if(factors[factors.size() - 1] % 4 == 3 && exp_cnt % 2 != 0) flag = false;
    return flag;
}

bool check3(ull n){
    while(n % 4 == 0) n /= 4;
    if(n % 8 != 7) return true;
    else return false;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    ull n; cin >> n;
    factorize(n);
    sort(factors.begin(), factors.end());
    
    
    if(check1()){
        // N이 1개의 제곱수로 표현 되는가
        cout << 1;
    }
    else if(check2()){
        // N이 2개의 제곱수로 표현 되는가
        // Fermat's Two-Square Theorem
        cout << 2;
    }
    else if(check3(n)){
        // N이 3개의 제곱수로 표현 되는가
        // Legendre's Three-Square Theorem
        cout << 3;
    }
    else{
        // N이 4개의 제곱수로 표현 되는가
        // Lagrange's Four-Square Theorem
        cout << 4;
    }
    return 0;
    
}