题解：高斯素因数分解（Gaussian Prime Factors）

一、题目分析

本题要求将正整数 ( n ) 分解为高斯素因数。高斯素数分为两类：

1. 实轴上的素数：形如 ( p )（( p ) 为素数且 ( p \equiv 3 \mod 4 )），如 ( 3, 7 )。
2. 复平面上的素数：形如 ( a + bj )（( a, b ) 为正整数且 ( a^2 + b^2 ) 为素数，且该素数 ( \equiv 1 \mod 4 ) 或为 ( 2 )），如 ( 1+j, 1+2j )。

二、核心思路

1. 素数分类判断：

   • 对于素数 ( p )，若 ( p = 2 ) 或 ( p \equiv 1 \mod 4 )，则可分解为复平面上的两个共轭高斯素数（如 ( 5 = (1+2j)(1-2j) )）。
   • 若 ( p \equiv 3 \mod 4 )，则 ( p ) 本身是高斯素数（实轴上的素数）。

2. 分解步骤：

   • 对 ( n ) 进行素因数分解，得到所有素因子。
   • 对每个素因子 ( p )，判断其类型并生成对应的高斯素因数。
   • 按题目要求排序输出结果。

三、代码解析

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

typedef long long llong;

struct complex {
    llong a, b; // 实部和虚部
    char op;    // 虚部符号（仅当 b≠0 时有效）
} c[1100];
llong cp; // 高斯素因数数组指针

// 排序规则：先按实部a升序，再按虚部b的绝对值升序，正虚部在前
bool cmp(complex m, complex n) {
    if (m.a != n.a) return m.a < n.a; // 实部优先
    if (abs(m.b) != abs(n.b)) return abs(m.b) < abs(n.b); // 虚部绝对值次优先
    return m.b > n.b; // 正虚部在前（如1+j排在1-j前）
}

// 处理素数p，生成对应的高斯素因数
void getResult(llong p) {
    if (p == 2) { // 特殊情况：2 = (1+j)(1-j)
        c[cp].a = 1, c[cp].b = 1, c[cp++].op = '+';
        c[cp].a = 1, c[cp].b = 1, c[cp++].op = '-';
        return;
    }
    if ((p % 4) == 1) { // p ≡1 mod4，可分解为a+bj和a-bj
        llong j = sqrt(p - 1); // 寻找a=1，b=j的情况（题目要求|b|≥a，a>0）
        for (llong i = 1; i * i < p; i++) {
            j = sqrt(p - i * i);
            if (i * i + j * j == p) {
                c[cp].a = i, c[cp].b = j, c[cp++].op = '+';
                c[cp].a = i, c[cp].b = -j, c[cp++].op = '+'; // 存储为负虚部，输出时处理符号
                break;
            }
        }
    } else { // p≡3 mod4，实轴上的高斯素数
        c[cp].a = p, c[cp].b = 0, c[cp++].op = '*'; // op无实际意义，仅用于标记
    }
}

int main() {
    llong in, num = 0;
    while (scanf("%lld", &in) != EOF) {
        cp = 0;
        llong tmpIn = in;
        printf("Case #%lld: ", ++num);
        
        // 分解素因数并处理
        for (llong i = 2; i * i <= tmpIn; i++) {
            if (tmpIn % i == 0) {
                getResult(i); // 处理素因子i
                while (tmpIn % i == 0) tmpIn /= i; // 去除所有i因子
            }
        }
        if (tmpIn > 1) getResult(tmpIn); // 处理剩余的素因子（若为1则忽略）
        
        // 排序
        sort(c, c + cp, cmp);
        
        // 输出结果
        for (llong i = 0; i < cp; i++) {
            if (i) printf(", ");
            if (c[i].b == 0) { // 实轴上的素数
                printf("%lld", c[i].a);
            } else { // 复平面上的素数
                printf("%lld%c%lldj", c[i].a, (c[i].b > 0 ? '+' : '-'), abs(c[i].b));
            }
        }
        printf("\n");
    }
    return 0;
}

四、关键点总结

1. 素数分解：

   • 对 ( n ) 进行试除法分解，得到所有素因子。
   • 对每个素因子 ( p )，根据 ( p \mod 4 ) 的结果判断其类型。

2. 高斯素因数生成：

   • 对于 ( p=2 ) 或 ( p \equiv 1 \mod 4 )，生成共轭对 ( a+bj ) 和 ( a-bj )，确保 ( a>0 ) 且 ( |b| \geq a )。
   • 对于 ( p \equiv 3 \mod 4 )，直接保留为实轴素数。

3. 排序规则：

   • 先按实部 ( a ) 升序，再按虚部绝对值升序，正虚部在前（如 ( 1+j ) 排在 ( 1-j ) 前）。

4. 输出处理：

   • 实轴素数直接输出 ( a )。
   • 复平面素数根据虚部符号输出 ( a+bj ) 或 ( a-bj )，确保格式正确。

该解法通过素因数分解和高斯素数分类，结合排序规则，高效地解决了高斯素因数分解问题，满足题目要求的输出格式和排序规则。