蓝桥杯 2019省赛 C/C++ A TE

知识点

扩展欧几里得算法/欧拉函数，快速乘与快速幂

题目

思路

本题按照题目所述算法计算，首先需要求得两个质数p、q，直接暴力遍历求得即可，耗时10s左右，之后求e需要通过扩展欧几里得算法或者欧拉函数计算逆元，最后求X需要通过快速幂计算，但由于n过大，快速幂中乘法需要替换为快速乘。

代码

#include <iostream>
#include <set>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long ll;

ll n = 1001733993063167141;

ll getP(ll n)
{
    for (ll i = 2; i < n; i++)
        if (n % i == 0)
            return i;
}

void exgcd(ll a, ll b, ll &d, ll &x, ll &y)
{
    if (!b)
    {
        d = a;
        x = 1;
        y = 0;
        return;
    }
    exgcd(b, a % b, d, y, x);
    y -= (a / b) * x;
}

ll rev(ll t, ll m)
{
    ll d, x, y;
    exgcd(t, m, d, x, y);
    return (x % m + m) % m;
}

ll fast_product(ll a, ll b, ll mod)
{
    ll ans = 0;
    while (b)
    {
        if (b & 1)
            ans = (ans + a) % mod;
        a = (a + a) % mod;
        b >>= 1;
    }
    return ans;
}

ll fast_pow(ll a, ll b, ll mod)
{
    ll ans = 1;
    while (b)
    {
        if (b & 1)
            ans = fast_product(ans, a, mod);
        fast_product(a, a, mod);
        b >>= 1;
    }
    return ans;
}

int main()
{
    ll p = getP(n);
    ll q = n / p;
    ll k = n - p - q + 1;
    ll d = 212353;
    ll e = rev(d, k);
    cout << "e=" << e << endl;
    ll C = 20190324;
    ll X = fast_pow(C, e, n);
    cout << "X=" << X << endl;
    return 0;
}