A.EhAb AnD gCd

题意：

给一个n，找一对数(x,y)使得 $gcd(x,y)+lcm(x,y)=n$

题解：

令x=1，y=n-1即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
char s[maxn];
void solve()
{
    int n;
    scanf("%d", &n);
    printf("%d %d\n", 1, n - 1);
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

B.CopyCopyCopyCopyCopy

题意：

给定一个序列 a ，并将这个序列复制无数份接在一起，求这个无限长序列中的最长上升子序列。

题解：

给定序列有多少不同元素就有多长。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 2e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
char s[maxn];
void solve()
{
    set<int> s;
    int n;
    scanf("%d", &n);
    for (int i = 0, x; i < n; i++)
    {
        scanf("%d", &x);
        s.insert(x);
    }
    printf("%d\n", s.size());
}
int main()
{
    int t;
    for (scanf("%d", &t); t >= 1; t--)
        solve();
}

C.Ehab and Path-etic MEXs（构造）

题意：

给一棵n个节点的树，树的边从0到n−2编号.定义 $MEX(u,v)$ 是说点u到v的路径上最小的未出现的标号（例如路径上的标号是0,2,3，那结果就是 1 ），给出一种构造方案使得对于所有 $MEX(u,v)$ 的最大值最小。

题解：

1、如果树是一条链，随便排。全链路径的MEX一定为n−1。
2、如果存在某一个节点度数大于3，选择其中三条边编号0，1，2。这样其他的路径一定不会同时经过0，1，2。而无论怎么排列，一定无法避免其中会有一条路径同时经过0，1。所以所有路径的MEX的最小值一定为2。其他的随便排就可以了。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
vector<pii> G[maxn];
int ans[maxn];
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i < n; i++)
    {
        int u, v;
        scanf("%d%d", &u, &v);
        G[u].push_back({v, i});
        G[v].push_back({u, i});
        ans[i] = -1;
    }
    int cnt = 0;
    for (int i = 1; i <= n; i++)
    {
        if (G[i].size() >= 3)
        {
            for (auto j : G[i])
                ans[j.second] = cnt++;
            for (int j = 1; j < n; j++)
                if (ans[j] == -1)
                    ans[j] = cnt++;
            for (int j = 1; j < n; j++)
                printf("%d\n", ans[j]);
            return 0;
        }
    }
    for (int i = 1; i < n; i++)
        printf("%d\n", i - 1);
    return 0;
}

D.Ehab the Xorcist（构造）

题意：

给定两个数字u和v，构造一个最短的数列 $a_n$ 满足 $图片说明$ 并且 $图片说明$

题解：

先讲特判。
1、u>v：不存在。
2、u,v奇偶性不同：不存在。
3、u=v=0：根据样例应该是0. $图片说明$
4、u=v≠0：一个元素等于u即可。
对于一般情况，先给出两条规律：
1、 $图片说明$
2、 $图片说明$
所以我们可以构造一个长度为3的序列{u,x,x},一定满足异或值为u，解得 $图片说明$ 。
注意到样例中存在长度为2的序列。那么继续操作。
若满足 $图片说明$ 则 $图片说明$ ,那么长度为2的序列也被我们构造出来了。
对其余情况长度一定不可能为2的证明：根据 $a+b=a⊕b+2×(a \& b)$ ,则 $a \& b=x$ 。那么除了上述情况不存在其他情况长度为2。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e5 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
int main()
{
    ll u, v;
    scanf("%lld%lld", &u, &v);
    if (u == 0 && v == 0)
    {
        puts("0");
        return 0;
    }
    if (u > v || ((u & 1) != (v & 1)))
    {
        puts("-1");
        return 0;
    }
    if (u == v)
    {
        puts("1");
        printf("%lld\n", u);
        return 0;
    }
    ll x = u, y = (v - u) >> 1;
    if ((x ^ y) == (x + y))
    {
        puts("2");
        printf("%lld %lld\n", x + y, y);
    }
    else
    {
        puts("3");
        printf("%lld %lld %lld\n", x, y, y);
    }
    return 0;
}

E.Ehab's REAL Number Theory Problem

题意：

给一个数组，每个元素因子数不超过7，求最短序列使积为完全平方数。

题解：

把每个 $a_i$ 的平方因子除尽后对答案没有影响，所以可以把每个 $a_i$ 的平方因子除尽。
如果某个 $a_i$ 的质因子除尽后为1，直接选它即可。
然后剩下的质因子的幂次肯定为 1，根据约数个数定理如果存在三个质因子，那么约数个数为 $(1+1)^{3}=8>7$ ,所以只会存在至多两个质因子，因此可以将每个数的质因子看作一条边，因为环的每个节点度数均为2，所以问题转化为求环，又要求最短序列，最终所求为最小环

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int maxn = 1e6 + 5;
const int INF = 0x3f3f3f3f;
const int mod = 998244353;
int n, ans = INF, dep[maxn], fa[maxn];
vector<int> G[maxn];
void div(int x)
{
    for (int i = 2; i * i <= x; i++)
        if (x % i == 0)
            while (x % (i * i) == 0)
                x /= i * i;
    if (x == 1)
        puts("1"), exit(0);
    int p1 = x, p2 = 1;
    for (int i = 2; i * i <= x; i++)
        if (x % i == 0)
            p1 = x / i, p2 = i;
    G[p1].push_back(p2);
    G[p2].push_back(p1);
}
void bfs(int x)
{
    memset(dep, INF, sizeof(dep));
    queue<int> q;
    dep[x] = 0;
    q.push(x);
    while (!q.empty())
    {
        int u = q.front();
        q.pop();
        for (auto v : G[u])
        {
            if (v == fa[u])
                continue;
            if (dep[v] == INF)
            {
                fa[v] = u;
                dep[v] = dep[u] + 1;
                q.push(v);
            }
            else
                ans = min(ans, dep[u] + dep[v] + 1);
        }
    }
}
int main()
{

    scanf("%d", &n);
    for (int i = 1, x; i <= n; i++)
    {
        scanf("%d", &x);
        div(x);
    }
    for (int i = 1; i <= 1000; i++)
        bfs(i);
    if (ans == INF)
        puts("-1");
    else
        printf("%d\n", ans);
    return 0;
}

F.Ehab's Last Theorem

题意：

给定一个 n 个点 m 条边的无向图。要求找出一个点数恰好为 $图片说明$ 的独立点集或者找出一个点数至少为 $图片说明$ 的环

题解：

首先，找环是很容易的，直接在 dfs 树上找返祖边（回边）即可，如果存在点数 $图片说明$ 的环就直接输出，类似于tarjan找环。然后再考虑独立集的构造，我们用 $图片说明$ 种颜色给给dfs树上的节点按照dep[i]%( $图片说明$ )的规则染色,那么在模下相同深度的节点构成的肯定是一个独立点集，而在模意义下相同的任意两个不同深度节点之间，如果存在直连边就说明存在一个节点数 $图片说明$ 的环。于是只要找一个 $图片说明$ 的集合输出 $图片说明$ 个点即可

#include <bits/stdc++.h>
using namespace std;
const int maxn = 2e5 + 5;
typedef long long ll;
const int inf = 0x3f3f3f3f;
int n, m, lim;
int dep[maxn], fa[maxn], num[maxn];
vector<int> G[maxn];
void dfs(int u)
{
    ++num[dep[u] % (lim - 1)];
    for (auto v : G[u])
    {
        if (v == fa[u])
            continue;
        if (dep[v] == -1)
        {
            dep[v] = dep[u] + 1;
            fa[v] = u;
            dfs(v);
        }
        else if (dep[u] - dep[v] + 1 >= lim)
        {
            puts("2");
            printf("%d\n", dep[u] - dep[v] + 1);
            for (int i = u; i != fa[v]; i = fa[i])
                printf("%d ", i);
            exit(0);
        }
    }
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 0; i <= n; i++)
        dep[i] = -1;
    dep[1] = 0;
    lim = ceil(sqrt(1.0 * n));
    for (int i = 1; i <= m; i++)
    {
        int x, y;
        scanf("%d%d", &x, &y);
        G[x].push_back(y);
        G[y].push_back(x);
    }
    dfs(1);
    puts("1");
    for (int i = 0; i < lim - 1; i++)
    {
        if (num[i] < lim)
            continue;
        int tot = lim;
        for (int j = 1; j <= n; j++)
        {
            if (dep[j] % (lim - 1) == i)
            {
                if (tot-- != lim)
                    printf(" ");
                printf("%d", j);
                if (tot == 0)
                    return 0;
            }
        }
    }
}

Codeforces Round #628 (Div. 2)