HDU 3826 Squarefree Number - 10^18 範圍內無平方因子判定

問題描述

判定整數 N (2 ≤ N ≤ 10¹⁸) 是否為無平方因子數（即不被除 1 外的任何完全平方數整除）。T ≤ 20 組測試。

核心觀察

若 N 有平方因子 p²，則 p ≤ √N ≤ 10⁹。但直接試除到 10⁹ 太慢。關鍵優化：
若 N 除盡所有 ≤ 10⁶ 的質數後餘數 > 1，則該餘數要么是質數，要么是兩個質數乘積（因若有三個質因子，最小乘積 > 10¹⁸）。故只需：

1. 篩選 10⁶ 內所有質數（約 7.8 萬個）
2. 試除這些質數，若某質數平方整除 N，直接返回 No
3. 剩餘值 > 10⁶ 時，檢查其是否為完全平方數

算法流程

// 1. 線性/埃氏篩生成質數表
// 2. 對每個測試數 N：
ok = true
for p in primes:
    if p*p > N: break
    cnt = 0
    while N % p == 0:
        N /= p; cnt++
        if cnt >= 2: ok = false; break
    if not ok: break
if ok and N > 1:
    x = (long long)sqrt(N)
    if x*x == N: ok = false  // 剩餘部分是平方數
output ok ? "Yes" : "No"

關鍵技術點

質數篩優化

使用 vis[j]=1 標記合數，m = sqrt(n) 為篩選上限。10⁶ 篩選極快（<10ms）。

大數開方精度

x = (long long)sqrt((double)N)，雙精度浮點數 53 位尾數足夠精確表示 10¹⁸ 內整數開方。

邊界情況

• N 本身是質數 > 10⁶：試除後 N 不變，sqrt 檢查通過 → Yes
• N = p² (p > 10⁶ 質數)：試除無果，sqrt 檢查發現完全平方 → No
• N = p×q (p,q > 10⁶ 不等質數)：試除無果，非完全平方 → Yes

代碼實現

#include <cstdio> #include <cstring> #include <cmath>
const int MAXN = 80000+10;
const int N = 1000000;
int prime[MAXN], vis[N];
__int64 N;
int pos;

int init() {
    int c = 0, m = sqrt(N + 0.5);
    memset(vis, 0, sizeof(vis));
    for (int i = 2; i <= m; i++)
        if (!vis[i])
            for (int j = i*i; j <= N; j += i) vis[j] = 1;
    for (int i = 2; i <= N; i++)
        if (!vis[i]) prime[c++] = i;
    return c;
}

int judge() {
    for (int i = 0; i < pos; i++) {
        while (N % prime[i] == 0) {
            N /= prime[i];
            if (N % prime[i] == 0) return 0;
        }
    }
    return 1;
}

int main() {
    pos = init();
    int t, cas = 1;
    scanf("%d", &t);
    while (t--) {
        __int64 x;
        int ok = 1;
        scanf("%I64d", &N);
        if (!judge()) ok = 0;
        if (N > 1000000) {
            x = (int)sqrt((double)N);
            if (x * x == N) ok = 0;
        }
        printf("Case %d: %s\n", cas++, ok ? "Yes" : "No");
    }
    return 0;
}

複雜度分析

• 預處理：O(N log log N) ≈ 10⁶ 操作
• 單次查詢：O(π(10⁶)) ≈ 7.8×10⁴ 次試除，T=20 總計 < 2×10⁶ 操作
• 記憶體：質數表 ~300KB，訪問數組 ~1MB

總結

本題展示了大數因數分解的經典策略：小質數試除 + 大餘數特殊性質判斷。利用「N ≤ 10¹⁸ 除盡小質數後餘數最多有兩個質因子」的數學結構，將問題降維到可行範圍。