CF995E Number Clicker

题目分析

首先，我们必须明白，操作都是互逆的,\(1,2\)之间是可以互相转化的，这是不需证明的，对于操作\(3\),实际上，是求当前数的逆元，我们知道，逆元就是求当前数在模另一个数下的倒数，那么，逆元的逆元就是他本身也就是倒数的倒数

于是，所有的操作是可以转化的，对于搜索，其实就有用双向\(bfs\)的依据

采用此算法，需要注意，反向的操作需要转化为现在的正向操作

其实，一共也不会运算超过五秒的时间

#include <bits/stdc++.h>

using namespace std;

long long Pow(long long a, long long b, long long mod) {

    long long base = a;

    long long ans = 1;

    while (b) {

        if (b & 1) {

            ans *= base;

            ans %= mod;

        }

        base *= base;

        base %= mod;

        b >>= 1;

    }

    return ans;

}

long long u, v, p;

struct node {

    long long sta;

	int  op;

    vector<int> opera;

};

map<long long, int> vis[5];

vector<int> last1, last2;

map<long long, vector<int> > step[5];

void Bfs_Both() {

    queue<node> q;

    node A;

    A.sta = u;

    A.op = 0;

    q.push(A);

    vis[0][A.sta] = 1;

    node B;

    B.sta = v;

    B.op = 1;

    vis[1][B.sta] = 1;

    q.push(B);

    while (q.size()) {

        node temp = q.front();

        q.pop();

        if (vis[(temp.op == 1) ? 0 : 1][temp.sta]) {

            last1 = step[0][temp.sta];

            last2 = step[1][temp.sta];

            return;

        }

        node ply;

        ply = temp;

        ply.sta = (temp.sta + 1) % p;

        if (!vis[ply.op][ply.sta]) {

            vis[ply.op][ply.sta] = 1;

            ply.opera.push_back(1);

            step[ply.op][ply.sta] = ply.opera;

            q.push(ply);

            ply.opera.pop_back();

        }

        ply.sta = (temp.sta - 1 + p) % p;

        if (!vis[ply.op][ply.sta]) {

            vis[ply.op][ply.sta] = 1;

            ply.opera.push_back(2);

            step[ply.op][ply.sta] = ply.opera;

            q.push(ply);

            ply.opera.pop_back();

        }

        ply.sta = Pow(temp.sta, p - 2, p);

        if (!vis[ply.op][ply.sta]) {

            vis[ply.op][ply.sta] = 1;

            ply.opera.push_back(3);

            step[ply.op][ply.sta] = ply.opera;

            q.push(ply);

            ply.opera.pop_back();

        }

    }

}

int main() {

    scanf("%lld %lld %lld", &u, &v, &p);

    Bfs_Both();

    printf("%d\n", last1.size() + last2.size());

    for (int i = 0; i < last1.size(); i++) {

        printf("%d ", last1[i]);

    }

    for (int i = last2.size()-1; i >=0 ; i--) {

    	if(last2[i]==1)

    	{

    		printf("2 ");

		}

		else if(last2[i]==2)

		{

			printf("1 ");

		}

		else

		{

			printf("%d ", last2[i]);

		}

    }

}

巴特西

CF995E Number Clicker

题目分析

最新文章

热门文章