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

8217

HINT

 

Source

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

目前这段代码能够AC

 #include <bits/stdc++.h>

 using namespace std;

 const int maxn = ;

 int a,b,p,tot,prime[maxn],uf[maxn];

 bool vis[maxn] = {true,true};

 void selectPrime(){

     for(int i = ; i < maxn; ++i){

         if(!vis[i]) prime[tot++] = i;

         for(int j = ; j < tot && prime[j]*i < maxn; ++j){

             vis[i*prime[j]] = true;

             if(i%prime[j] == ) break;

         }

     }

 }

 int Find(int x){

     int t = x;

     while(uf[x] != x) x = uf[x];

     while(uf[t] != t){

         int tmp = uf[t];

         uf[t] = x;

         t = tmp;

     }

     return x;

 }

 int main(){

     selectPrime();

     while(~scanf("%d %d %d",&a,&b,&p)){

         if(a > b) swap(a,b);

         if(p > b){

             printf("%d\n",b - a + );

             continue;

         }

         for(int i = a; i <= b; ++i) uf[i] = i;

         for(int i = ; i < tot && prime[i] <= b; ++i){

             if(prime[i] >= p){

                 int t = a/prime[i]*prime[i];

                 while(t < a) t += prime[i];

                 int s = t + prime[i];

                 while(s <= b){

                     int x = Find(t);

                     int y = Find(s);

                     if(x != y) if(i&) uf[x] = y;else uf[y] = x;

                     s += prime[i];

                 }

             }

         }

         int ans = ;

         for(int i = a; i <= b; ++i)

             if(uf[i] == i) ans++;

         printf("%d\n",ans);

     }

     return ;

 }

已经改成3s了