對撞機_紀中3074_暴力？

Description

在2312年，宇宙中發現了n台巨型對撞機，這些對撞機分别用1-n的自然數辨別。科學家們不知道啟動這些對撞機會發生什麼危險事故，是以這些機器，剛開始都是處于關閉狀态。

随着科學家們的研究發現，第i台對撞機啟動是安全的，如果其他已經啟動的對撞機的辨別數都跟這台對撞機标志數互質。（例如假設前面啟動的是j,如果i能啟動，那麼(I,j)互為質數，也就是（I,j）的最大公約數為1）!如果兩台對撞機不互為質數就啟動，那麼就會發生爆炸事故。

基于前面的研究，科學家們準備做各種啟動和關閉對撞機的實驗，為了確定科學家的生命安全。你要設計一個遠端遙控的軟體。剛開始，所有的對撞機都是關閉狀态。你的程式将會收到許多詢問，格式為“啟動/關閉第i台對撞機”。這程式應該能處理這些詢問（根據收到詢問的先後順序處理）。這程式應該按照如下的格式輸出處理結果。

如果詢問是”+ i”（表示第i台對撞機啟動），這程式應該按照下面三種的情況之一輸出結果。

1. “Success”，如果啟動第i台是安全的
2. “Already on”,如果第i在這個詢問之前就已經啟動了。

3. “Conflict with j”，如果第i台跟前面啟動了的第j台沖突，就不能啟動第I，如果前面有多台跟i沖突，那麼隻要輸出其中任何一台就可以。

   如果詢問是”-i”（表示關閉第i台對撞機）,這程式應該按照下面兩種的情況之一輸出結果。

4. “Success”,表示關閉第i台對撞機
5. “Already off”，表示第i台對撞機在詢問之前就已經關閉了。

Input

第一行輸入兩個空格隔開的整數n和m（1≤n,m≤10^5）分别表示對撞機的數量和詢問數。接下來m行表示詢問，每行要麼為“+ i”，要麼為“- i”（不含引号）（1≤i≤n）

Output

輸出m行，輸出結果按照上面題目給定格式輸出。

Analysis

關于判斷兩數字是否互質的方法：

1. 分解質因數
2. 檢查是否有相同的質因數

n不大，可以用一個桶儲存質因數，記錄沖突的情況

會有特殊情況，即n個質數，是以提前判斷一下是不是質數就好了，用 O(n−−√) 換 O(n) ，大概亂搞一下就可以了

洛谷有原題但是沒有spj←_←不要問我怎麼知道的

Code

#include <stdio.h>
using namespace std;
bool t[];
int v[];
int f[];
int pal(int k,int tmp)
{
    f[]=;
    int b=tmp?k:;
    while (k>)
    {
        for (int i=;i<=k;i++)
            if (!(k%i))
            {
                if (v[i]&&tmp==)
                    return v[i];
                f[++f[]]=i;
                k/=i;
                break;
            }
    }
    for (int i=;i<=f[];i++)
        v[f[i]]=b;
    return ;
}
int palidrome(int x)
{
    if (x%==)
        return ;
    for (int i=;i*i<=x;i+=)
        if (x%i==)
            return ;
}
int main()
{
    int n,m,k,tmp;
    scanf("%d%d",&n,&m);
    for (int i=;i<=m;i++)
    {
        char c[];
        scanf("%s%d",&c,&k);
        if (palidrome(k)&&!v[k])
        {
            printf("Success\n");
            t[k]=true;
            v[k]=k;
            continue;
        }
        if (c[]=='+')
        {
            if (t[k])
                printf("Already on\n");
            else
            {
                tmp=pal(k,);
                if (tmp)
                    printf("Conflict with %d\n",tmp);
                else
                {
                    printf("Success\n");
                    t[k]=true;
                }
            }
        }
        else
        {
            if (!t[k])
                printf("Already off\n");
            else
            {
                printf("Success\n");
                pal(k,);
                t[k]=false;
            }
        }
    }
    return ;
}