[UVA][建表、枚舉] 11099 - Next Same-Factored
Problem
F
Next
Same-Factored
Time Limit: 6 Seconds
Just print out the next integer number which has the same prime factors as the given number and is less than 2,000,000.
Input
There will be several test cases (at most 100,000). Each case is a single positive integer n that is less than 1,000,000, on a separate line.
Output
For each test case, output a line containing a single integer which is the next integer number that have the same prime factors as n. In the case that there is no such number print one line stating "Not Exist!".
Sample Input Output for Sample Input
2
143991 |
4
1573
982081
|
Special Thanks to: Ali Sharifrazavian
Alternate Solution: Ali Sharifrazavian, Hadi Moshayedi
1st Amirkabir UT Annual Programming Contest Qualification Round
題目描述：
要求找到下一個比 n 大的數字，且與 n 具有相同質因數的集合。
解法1：
建表，將每個數字的質因數(不管次方)找出來，將每個數字的質因數乘起來表示成一個數字 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;
}