CSUOJ 1644 超能陆战队

1644: 超能陆战队

Time Limit: 1 Sec Memory Limit: 256 MB
Submit: 6 Solved: 1
[Submit][Status][Web Board]

Description

在与卡拉汉教授的决战中，小宏发明的微型机器人与小白最后都被吸入了空洞。然而，若干年后的一个下午，大白带着小宏的微型机器人回来了！与大白再次相聚的小宏激动不已。可是由于空洞的强大吸力，微型机器人已经部分损坏，不能像以前一样很好的合体了。当任意两个微型机器人的编号存在不小于p的公共质因子时，他们就能合并！微型机器人都是从x开始连续编号的，并且最后一个微型机器人的编号为y。现在给出p，小宏想知道合体后最少能形成几个机器人

Input

每个样例一行，分别为x,y,p
0 <= x,y <= 1000000
p <= 1000000

Output

每个样例输出一行

Sample Input

20 100000 6

Sample Output

HINT

Source

解题：并查集乱搞下，TLE不是我的本意，我不知道CSUOJ的服务器到底跑多快，以及是否开启了o2，所以没有设置时限，谁知OJ管理童鞋竟然只给了1s

目前这段代码能够AC

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 1000010;
 4 int a,b,p,tot,prime[maxn],uf[maxn];
 5 bool vis[maxn] = {true,true};
 6 void selectPrime(){
 7     for(int i = 2; i < maxn; ++i){
 8         if(!vis[i]) prime[tot++] = i;
 9         for(int j = 0; j < tot && prime[j]*i < maxn; ++j){
10             vis[i*prime[j]] = true;
11             if(i%prime[j] == 0) break;
12         }
13     }
14 }
15 int Find(int x){
16     int t = x;
17     while(uf[x] != x) x = uf[x];
18     while(uf[t] != t){
19         int tmp = uf[t];
20         uf[t] = x;
21         t = tmp;
22     }
23     return x;
24 }
25 int main(){
26     selectPrime();
27     while(~scanf("%d %d %d",&a,&b,&p)){
28         if(a > b) swap(a,b);
29         if(p > b){
30             printf("%d
",b - a + 1);
31             continue;
32         }
33         for(int i = a; i <= b; ++i) uf[i] = i;
34         for(int i = 0; i < tot && prime[i] <= b; ++i){
35             if(prime[i] >= p){
36                 int t = a/prime[i]*prime[i];
37                 while(t < a) t += prime[i];
38                 int s = t + prime[i];
39                 while(s <= b){
40                     int x = Find(t);
41                     int y = Find(s);
42                     if(x != y) if(i&1) uf[x] = y;else uf[y] = x;
43                     s += prime[i];
44                 }
45             }
46         }
47         int ans = 0;
48         for(int i = a; i <= b; ++i)
49             if(uf[i] == i) ans++;
50         printf("%d
",ans);
51     }
52     return 0;
53 }

View Code

已经改成3s了