Codeforces Round #843 (Div. 2)

C. Interesting Sequence(二进制)

题目大意
给定两个大于等于0的数\(n,\ x\)，求满足\(n\&(n+1)\&(n+2)\cdots m=x\)的最小\(m\)，若不存在输出-1。

解题思路
首先若\(n<x\)肯定无解。
令\(l=n,\ r=5e18\)，若解存在那么它必定处在\([l,r]\)中。
一次考虑二进制中\(n,\ x\)中的每一位，

• 若\(n[i]==0\ \&\&\ x[i]==1\)，无解(若\(n<x\)必然会出现这种情况)。
• 若\(n[i]==0\ \&\&\ x[i]==0\)，无要求。
• 若\(n[i]==1\ \&\&\ x[i]==0\)，此时至少有一个参与运算的数字第\(i\)位为0，那么\(l = max(l, ((n >> i) + 1 << i))\)，此时在\(l\)的左边必定无解。
• 若\(n[i]==0\ \&\&\ x[i]==1\)，此时所有参与运算的数字第\(i\)位为1，那么\(r = min(r, ((n >> i) + 1 << i) - 1)\)，在\(r\)右边无解。

最后若\(l <= r\)则输出\(l\)(\(l\)记录的是检验每个二进制位后的可行解)，否则无解。

参考代码

#include <bits/stdc++.h>
using namespace std;
#define ll long long
void work()
{
    ll n, x;
    cin >> n >> x;
    ll l = n, r = 5e18;
    if (n < x)
    {
        cout << "-1" << endl;
        return ;
    }
    if (n == x)
    {
        cout << n << endl;
        return ;
    }
    bitset<64> a(n), b(x);
    for (int i = 63; i >= 0; --i)
    {
        if (a[i] == 0 && b[i] == 0)
            continue;
        else if (a[i] == 0 && b[i] == 1)
        {
            cout << "-1" << endl;
            return ;
        }
        else if (a[i] == 1 && b[i] == 0)
        {
            l = max(l, ((n >> i) + 1 << i));
        }
        else
        {
            r = min(r, ((n >> i) + 1 << i) - 1);
        }
    }
    if (l <= r)
    {
        cout << l << endl;
    }
    else
    {
        cout << "-1" << endl;
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T;
    cin >> T;
    while (T--)
    {
        work();
    }
    return 0;
}

D. Friendly Spiders(数论，图论)

题目大意
给定一张有向图，边的权值为1，每个节点\(i\)的权值为\(a_i\)，只有\(gcd(a_i,a_j)\neq 1\)的两点之间有边。
求给定两点之间的最短路径。

解题思路
求最短路径很简单，用\(bfs\)即可，关键是如何快速建边。
将原来的图改造成二分图，左边是原来的点，右边是质因子构成的集合，将左边的点与其所有的质因子连线。
原来的图结构事实上并没有被破坏，只是两点之间的距离变为了原来的两倍。但这大大减少了边的数量。

参考代码

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
int pri[N], cnt_p;
int book[N];
int n, s, t;
struct 
{
    int v, next;
}e[N * 20];
int cnt, head[N * 2];//质数偏移量加N
void get_p()
{
    for (int i = 2; i < N; ++i)
    {
        if (!book[i])
        {
            pri[cnt_p++] = i;
        }
        for (int j = 0; pri[j] * i < N; ++j)
        {
            book[pri[j] * i] = 1;
            if (i % pri[j] == 0)
                break;
        }
    }
}
void add(int u, int v)
{
    e[++cnt].next = head[u];
    e[cnt].v = v;
    head[u] = cnt;
}
int trace[N * 2], dis[N * 2];
bool vis[N * 2];
queue<int> q;
bool bfs()
{
    q.push(s);
    vis[s] = 1;
    int v;
    while (q.size())
    {
        int u = q.front();
        if (u == t)
            return true;
        q.pop();
        for (int i = head[u]; i; i = e[i].next)
        {
            v = e[i].v;
            if (vis[v])
                continue;
            dis[v] = dis[u] + 1;
            trace[v] = u;
            vis[v] = 1;
            q.push(v);
        }
    }
    return false;
}
void out(int u)
{
    if (u == s)
    {
        cout << s;
        return ;
    }
    else
    {
        out(trace[u]);
        if (u < N)
            cout << " " << u;
    }
}
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    get_p();
    cin >> n;
    int tt;
    for (int i = 1; i <= n; ++i)
    {
        cin >> tt;
        for (int j = 0; j < cnt_p && pri[j] * pri[j] <= tt; ++j)
        {
            if (tt % pri[j] == 0)
            {
                add(i, pri[j] + N);
                add(pri[j] + N, i);
                while (tt % pri[j] == 0)
                {
                    tt /= pri[j];
                }
            }
        }
        if (tt > 1)
        {
            add(i, tt + N);
            add(tt + N, i);
        }
    }
    cin >> s >> t;
    if (bfs())
    {
        cout << dis[t] / 2 + 1 << endl;
        out(t);
    }
    else
    {
        cout << "-1" << endl;
    }
    return 0;
}