POJ 3307 Smart Sister：丑數打表與因子生成數

問題描述

求第 i 個「只含因子 2,3,5,7」的數（即 7-smooth numbers）。多組查詢，i ≤ 66062。

打表法：多指針動態生成

維護四個指針 p2,p3,p5,p7，分別指向下一個待乘 2/3/5/7 的數。每次取四者最小值作為下一個丑數，並前移對應指針（相等時多指針同步前移）。

代碼實現

typedef unsigned long long ULL;
const int MAXL = 66062;
ULL a[MAXL+10];

ULL min4(ULL a,ULL b,ULL c,ULL d) {
    return min(min(a,b),min(c,d));
}

int main() {
    a[1]=1;
    int p2=1,p3=1,p5=1,p7=1;
    for (int i=2;i<=MAXL;i++) {
        ULL t = min4(a[p2]*2, a[p3]*3, a[p5]*5, a[p7]*7);
        a[i]=t;
        if (t==a[p2]*2) p2++;
        if (t==a[p3]*3) p3++;
        if (t==a[p5]*5) p5++;
        if (t==a[p7]*7) p7++;
    }
    int T; scanf("%d",&T);
    while (T--) {
        int i; scanf("%d",&i);
        printf("%llu\n", a[i]);
    }
    return 0;
}

關鍵點

• 預計算所有查詢所需最大索引（66062），O(1) 回答。
• 四指針法保證有序、無重複生成。
• 用 unsigned long long 防溢出（第 66062 個數約 2.6e18）。

複雜度

預計算 O(MAXL)，查詢 O(1)，極快。

總結

POJ 3307 是「多指針生成有序序列」的教科書例題。同類問題（如只含 2,3,5 的經典丑數）皆可用此模板。關鍵在於識別「每個新數由舊數乘質因子得到」的動態規劃性質。