2

-1
1 2

8

1 2
1 3
2 4
2 5
3 6
4 7
4 8
1 2
1 3
2 4
2 5
2 6
3 7
6 8

2 seconds

256 megabytes

standard input

standard output

#include <bits/stdc++.h>

using namespace std;

#define INF 0x7fffffff

//Prim算法实现

void la(int n)

{

    char f[];

   static char c[]= {'','','','','','','','','','','A','B','C','D','E','F'};

    int l=;

    while(n) {

        f[l++]=c[n%];

        n=n/;

    }

    for(int k=; k<l; k++)

    printf("%c ",f[k]);

    cout<<"\n";

}

void prim_test()

{

    freopen("out.txt","w",stdout);

    for(int n=; n<=; n++)

    {

        vector<vector<int> > A(n, vector<int>(n));

        for(int k=; k<n; k++)

            for(int l=k+; l<n; l++)

            {

                int cost=l^k;

                A[k][l] = cost;

                A[l][k] = cost;

            }

        int pos, minimum;

        int min_tree = ;

        vector<int> visited, lowcost;

        for (int i = ; i < n; ++i)

        {

            visited.push_back();    //初始化为0，表示都没加入

        }

        visited[] = ;   //最小生成树从第一个顶点开始

        for (int i = ; i < n; ++i)

        {

            lowcost.push_back(A[][i]);    //权值初始化为0

        }

        for (int i = ; i < n; ++i)      //枚举n个顶点

        {

            minimum = INF;

            for (int j = ; j < n; ++j)      //找到最小权边对应顶点

            {

                if(!visited[j] && minimum > lowcost[j])

                {

                    minimum = lowcost[j];

                    pos = j;

                }

            }

            if (minimum == INF)    //如果min = INF表示已经不再有点可以加入最小生成树中

                break;

            min_tree += minimum;

            visited[pos] = ;     //加入最小生成树中

            for (int j = ; j < n; ++j)

            {

                if(!visited[j] && lowcost[j] > A[pos][j]) lowcost[j] = A[pos][j];   //更新可更新边的权值

            }

        }

        la(min_tree);

    }

}

int main(void)

{

    prim_test();

    return ;

}

#include <bits/stdc++.h>

using namespace std;

long long la(long long m)

{

    if(m==)return ;

    return 2LL*la(m/)+(m+)/;

}

int main()

{

    long long n;

    cin>>n;

    cout<<la(n-);

    return ;

}

Mahmoud has an array a consisting of n integers. He asked Ehab to find another array b of the same length such that:

• b is lexicographically greater than or equal to a.
• bi ≥ 2.
• b is pairwise coprime: for every 1 ≤ i < j ≤ n, bi and bj are coprime, i. e. GCD(bi, bj) = 1, where GCD(w, z) is the greatest common divisor of w and z.

Ehab wants to choose a special array so he wants the lexicographically minimal array between all the variants. Can you find it?

An array x is lexicographically greater than an array y if there exists an index i such than xi > yi and xj = yj for all 1 ≤ j < i. An array x is equal to an array y if xi = yi for all 1 ≤ i ≤ n.

The first line contains an integer n (1 ≤ n ≤ 105), the number of elements in a and b.

The second line contains n integers a1, a2, ..., an (2 ≤ ai ≤ 105), the elements of a.

Output n space-separated integers, the i-th of them representing bi.

Note that in the second sample, the array is already pairwise coprime so we printed it.

预处理素数，然后模拟

#include <bits/stdc++.h>

using namespace std;

const int N=;

vector<int> d[N];

int p[N],vis[N];

int ok(int x)

{

    int ret=;

    for(auto i:d[x])

    ret&=!vis[i];

    return ret;

}

int main()

{

    int n;

    cin>>n;

    for(int i=;i<N;i++)

        if (!p[i])

        {

            for(int x=i;x<N;x+=i)d[x].push_back(i),p[x]=;

        }

    int f=,cur=;

    for(int i=,x;i<n;i++)

    {

        cin>>x;

        int out=x;

        if(f)

        {

            while(!ok(out))

            out++;

            if(out!=x)f=;

        }

        else

        {

            while(!ok(cur))cur++;

            out=cur;

        }

        printf("%d ",out);

        for(auto x:d[out])

        vis[x]=;

    }

}