2

143

991

4

1573

982081

1st Amirkabir UT Annual Programming Contest  Qualification Round

建表，將每個數字的質因數(不管次方)找出來，將每個數字的質因數乘起來表示成一個數字 v，
因此會有兩個屬性 n, v,
例如 n = 2^3 * 5^2 * 7^5, 則 v = 2*5*7

那麼排序一下，二分搜尋答案。

由於高達 200 萬的排序，因此處理上很慢，O(nlogn), 至少要跑 500 ms

#include <stdio.h>
#include <algorithm>
using namespace std;
#define maxL (2000000>>5)+1
#define GET(x) (mark[(x)>>5]>>((x)&31)&1)
#define SET(x) (mark[(x)>>5] |= 1<<((x)&31))
int mark[maxL];
struct E {
    int n, pi;
    bool operator<(const E &a) const {
        if(pi != a.pi)
            return pi < a.pi;
        return n < a.n;
    }
};
E D[2000005];
int S[2000005];
void sieve() {
    register int i, j, k;
    SET(1);
    int n = 2000000;
    for(i = 2; i <= n; i++)
        D[i].n = i, D[i].pi = 1;
    for(i = 2; i <= n; i++) {
        if(!GET(i)) {
            D[i].pi = i;
            for(k = n/i, j = i*k; k >= 2; k--, j -= i) {
                D[j].pi *= i;
                SET(j);
            }
        }
        S[i] = D[i].pi;
    }
    D[0].pi = 0;
    D[1].pi = 1;
}
int main() {
    sieve();
    long long n;
    return 0;
    sort(D, D+2000001);
    int i;
    while(scanf("%lld", &n) == 1) {
        if(n < 2) {
            puts("Not Exist!");
            continue;
        }
        E test;
        test.n = n, test.pi = S[n];
        int pos = upper_bound(D, D+2000001, test) - D;
        if(pos <= 2000000 && D[pos].pi == test.pi)
            printf("%d\n", D[pos].n);
        else
            puts("Not Exist!");
    }
    return 0;
}

解法2：

仔細想想，乾脆求出質因數，然後枚舉次方，根據輸入筆數，枚舉就會來得有效率，
由於具有相同質因數的數字小於 200 萬，至多只有約 300 個。

#include <stdio.h>
#include <algorithm>
using namespace std;
#define maxL (1000>>5)+1
#define GET(x) (mark[(x)>>5]>>((x)&31)&1)
#define SET(x) (mark[(x)>>5] |= 1<<((x)&31))
int mark[maxL];
int pm[1000], pt = 0;
void sieve() {
    register int i, j, k;
    SET(1);
    int n = 1000;
    for(i = 2; i <= n; i++) {
        if(!GET(i)) {
            pm[pt++] = i;
            for(k = n/i, j = i*k; k >= i; k--, j -= i)
                SET(j);
        }
    }
}
int f[1000], fidx, ret;
int n, m;
int i, j, k;
void dfs(int idx, long long mult) {
    if(idx == fidx) return;
    for(; mult <= ret; mult *= f[idx]) {
        dfs(idx+1, mult);
        if(mult > n)
            ret = min(ret, (int)mult);
    }
}
int main() {
    sieve();
    while(scanf("%d", &n) == 1) {
        if(n < 2) {
            puts("Not Exist!");
            continue;
        }
        m = n;
        fidx = 0;
        int base = 1;
        for(i = 0; i < pt && pm[i]*pm[i] <= m; i++) {
            j = pm[i];
            if(m%j == 0) {
                k = 0;
                while(m%j == 0) k++, m /= j;
                f[fidx++] = j, base *= j;
            }
        }
        if(fidx == 0) {//prime
            if(n > 1414)
                puts("Not Exist!");
            else
                printf("%d\n", n*n);
            continue;
        }
        if(m != 1)
            f[fidx++] = m, base *= m;
        ret = 2000000;
        dfs(0, base);
        if(ret < 2000000)
            printf("%d\n", ret);
        else
            puts("Not Exist!");
    }
    return 0;
}

您可能對以下文章有興趣

[UVA][二分圖檢查] 11396 - Claw Decomposition

[UVA] 1419 - Ugly Windows

[UVA][ST] 12532 - Interval Product

[UVA] 440 - Eeny Meeny Moo