回复 127楼 czz5242199
Thank You,我原来是忘记0了。
编程之路定要走完……
Problem 1202 - Meepo's problem II
Problem 1202 - Meepo's problem II
Time Limit: 1000MS Memory Limit: 131072KB Difficulty:
Total Submit: 2 Accepted: 1 Special Judge: No
Description
Meepo the Geomancer is a mischievous spirit of the earth who enjoys burying his enemies alive in mountains of rock spikes.We all know that Meepo can summons some duplicate of himself,the clones are independent to each other and have the same abilities as Meepo.
When the Kth Meepo clone be summoned, this clone gain F(K,D) extra damage.
Here F(K,D) means the Kth small prime factor of D,where D is the primary Meepo's damage.
For example if primary Meepo's damage is 12, F(1,12) = 2.
And if K is bigger than the numbers of D's prim factor, F(K,D) = D.
Now if Meepo's damge range is [Li , Ri] , he want to know his Kth clone's
damage range.
Input
First line a number n (n<=100000),means Meepo's query.
Next n line, 3 positive integer a line: Li,Ri,K ,means Meepo's damage range is [Li,Ri],
and he wants to know his Kth clone's damage range.
All Li,Ri,and K are no more than 500000 and Li<=Ri.
Output
For every query, print two integer [L,R],means Meepo's clone's damage range.
Sample Input
3
17 47 3
11 36 7
3 16 1
Sample Output
34 94
22 72
6 26
Hint
Source
eggeek
分析Time Limit: 1000MS Memory Limit: 131072KB Difficulty:
Total Submit: 2 Accepted: 1 Special Judge: No
Description
Meepo the Geomancer is a mischievous spirit of the earth who enjoys burying his enemies alive in mountains of rock spikes.We all know that Meepo can summons some duplicate of himself,the clones are independent to each other and have the same abilities as Meepo.
When the Kth Meepo clone be summoned, this clone gain F(K,D) extra damage.
Here F(K,D) means the Kth small prime factor of D,where D is the primary Meepo's damage.
For example if primary Meepo's damage is 12, F(1,12) = 2.
And if K is bigger than the numbers of D's prim factor, F(K,D) = D.
Now if Meepo's damge range is [Li , Ri] , he want to know his Kth clone's
damage range.
Input
First line a number n (n<=100000),means Meepo's query.
Next n line, 3 positive integer a line: Li,Ri,K ,means Meepo's damage range is [Li,Ri],
and he wants to know his Kth clone's damage range.
All Li,Ri,and K are no more than 500000 and Li<=Ri.
Output
For every query, print two integer [L,R],means Meepo's clone's damage range.
Sample Input
3
17 47 3
11 36 7
3 16 1
Sample Output
34 94
22 72
6 26
Hint
Source
eggeek
我魔兽玩的很烂。在同事的诱惑下玩了几次，不过发现自己真没这方面的天赋。相比自己去玩我更愿意看他们玩（更准确点是听），我这帮同事打魔兽时太有意思了，跟说相声似的。
书归正传，这个题目涉及两方面的计算，一是因式分解，另一个是最大最小值的检索。
由于数据量很大，所以直接的检索是行不通的。
直接检索的时间复杂度为O(n*m)。n是测试数据组数,m是检索范围，两个参数的上限都很大，所以轻松超时。
对此可以使用线段树来提高检索效率，将时间复杂度降到O(n * log(m))。
至于因式分解，可以改造一下素数筛来完成。
书归正传，这个题目涉及两方面的计算，一是因式分解，另一个是最大最小值的检索。
由于数据量很大，所以直接的检索是行不通的。
直接检索的时间复杂度为O(n*m)。n是测试数据组数,m是检索范围，两个参数的上限都很大，所以轻松超时。
对此可以使用线段树来提高检索效率，将时间复杂度降到O(n * log(m))。
至于因式分解，可以改造一下素数筛来完成。
程序代码：#include<stdio.h>
#define MAX_RANGE 500000
#define MAX_FN 7
struct
{
int L, R;
int max[MAX_FN];
int min[MAX_FN];
int il, ir;
} ST[MAX_RANGE * 2];
int FL, FR, K;
void build_tree(int L, int R, int root)
{
static int ip = MAX_RANGE + 1;
int i;
ST[root].L = L;
ST[root].R = R;
i = (L + R) >> 1;
if(i == L) ST[root].il = L; else build_tree(L, i, ST[root].il = ip++);
if(i + 1 == R) ST[root].ir = R; else build_tree(i + 1, R, ST[root].ir = ip++);
for(i = 0; i < MAX_FN; i++)
{
ST[root].max[i] = ST[ST[root].il].max[i] > ST[ST[root].ir].max[i] ? ST[ST[root].il].max[i] : ST[ST[root].ir].max[i];
ST[root].min[i] = ST[ST[root].il].min[i] < ST[ST[root].ir].min[i] ? ST[ST[root].il].min[i] : ST[ST[root].ir].min[i];
}
}
void init()
{
int i, j, t;
ST[1].L = ST[1].R = 1;
for(i = 0; i < MAX_FN; i++) ST[1].max[i] = ST[1].min[i] = 2;
for(i = 2; i <= MAX_RANGE; i++)
{
ST[i].L = ST[i].R = i;
if(!ST[i].il)
for(j = i + i; j <= MAX_RANGE; ST[j].il++, j += i) ST[j].max[ST[j].il] = ST[j].min[ST[j].il] = i + j;
for(t = i + i, j = ST[i].il; j < MAX_FN; j++) ST[i].max[j] = ST[i].min[j] = t;
}
build_tree(1, MAX_RANGE, 0);
}
void search(int L, int R, int root)
{
if(L > ST[root].R || R < ST[root].L) return;
if(L <= ST[root].L && R >= ST[root].R)
{
if(FL > ST[root].min[K]) FL = ST[root].min[K];
if(FR < ST[root].max[K]) FR = ST[root].max[K];
return;
}
if(L < ST[root].L) L = ST[root].L;
if(R > ST[root].R) R = ST[root].R;
search(L, R, ST[root].il);
search(L, R, ST[root].ir);
}
void output(int L, int R)
{
FL = MAX_RANGE * 2;
FR = 1;
K = K > MAX_FN ? MAX_FN - 1 : K - 1;
search(L, R, 0);
printf("%d %d\n", FL, FR);
}
int main()
{
int n, Li, Ri;
init();
for(scanf("%d", &n); n--; output(Li, Ri))
scanf("%d%d%d", &Li, &Ri, &K);
return 0;
}
