51Nod-1038-X^A Mod P

ACM模版

描述

题解

第一次接触原根这个玩意儿,感觉真恶心,一脸懵逼啊……

leader_win’s blog 讲得倒是十分详细,可是我依然懵逼着,数论真的恶心,太多太多╮(╯﹏╰)╭……

代码

#include <cmath>
#include <vector>
#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

typedef long long ll;

const int MAXN = 100100;

ll qk_pow(ll a, ll b, ll mod)
{
    ll ret = 1;
    while (b)
    {
        if (b & 1)
        {
            ret = ret * a % mod;
        }
        b >>= 1;
        a = a * a % mod;
    }
    return ret;
}

ll ex_gcd(ll a, ll b, ll &x, ll &y)
{
    if (b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    else
    {
        ll r = ex_gcd(b, a % b, y, x);
        y -= x * (a / b);
        return r;
    }
}

vector<ll> a;

bool check(ll g, ll p)
{
    for (int i = 0; i < a.size(); i++)
    {
        if (qk_pow(g, (p - 1) / a[i], p) == 1)
        {
            return 0;
        }
    }

    return 1;
}

//  求解原根
ll primitive_root(ll p)
{
    ll tmp = p - 1;
    for (int i = 2; i <= tmp / i; i++)
    {
        if (tmp % i == 0)
        {
            a.push_back(i);
            while (tmp % i == 0)
            {
                tmp /= i;
            }
        }
    }
    if (tmp != 1)
    {
        a.push_back(tmp);
    }

    ll g = 1;
    while (true)
    {
        if (check(g, p))
        {
            return g;
        }
        ++g;
    }
}

struct sa
{
    ll x;
    int id;
    bool operator < (const sa &b) const
    {
        if (x == b.x)
        {
            return id < b.id;
        }
        return x < b.x;
    }
} rec[MAXN];

//  求解离散对数
ll discerte_log(ll x, ll n, ll m)
{
    int s = (int)(sqrt((double)m + 0.5));
    while ((ll)s * s <= m)
    {
        s++;
    }

    ll cur = 1;
    sa tmp;
    for (int i = 0; i < s; i++)
    {
        tmp.x = cur;
        tmp.id = i;
        rec[i] = tmp;
        cur = cur * x % m;
    }

    sort(rec, rec + s);
    ll mul = qk_pow(cur, m - 2, m) % m;
    cur = 1;

    for (int i = 0; i < s; i++)
    {
        ll more = n * cur % m;
        tmp.x = more;
        tmp.id = -1;
        int j = (int)(lower_bound(rec, rec + s, tmp) - rec);
        if (rec[j].x == more)
        {
            return i * s + rec[j].id;
        }

        cur = cur * mul % m;
    }

    return -1;
}

//  求解n次剩余
vector<ll> residue(ll p, ll n, ll a)
{
    vector<ll> ret;
    if (a == 0)
    {
        ret.push_back(0);
        return ret;
    }

    ll g = primitive_root(p);
    ll m = discerte_log(g, a, p);

    if (m == -1)
    {
        return ret;
    }

    ll A = n, B = p - 1, C = m, x, y;
    ll G = ex_gcd(A, B, x, y);
    if (C % G != 0)
    {
        return ret;
    }

    x = x * (C / G) % B;
    ll delta = B / G;
    for (int i = 0; i < G; i++)
    {
        x = ((x + delta) % B + B) % B;
        ret.push_back(qk_pow(g, x, p));
    }
    sort(ret.begin(), ret.end());
    ret.erase(unique(ret.begin(), ret.end()), ret.end());

    return ret;
}

ll P, A, B;

int main()
{
    int T;
    scanf("%d", &T);

    while (T--)
    {
        a.clear();
        scanf("%lld%lld%lld", &P, &A, &B);

        vector<ll> ans;
        ans = residue(P, A, B);

        if (ans.empty())
        {
            puts("No Solution");
        }
        else
        {
            for (int i = 0; i < ans.size(); i++)
            {
                printf("%lld ", ans[i]);
            }
            putchar(10);
        }
    }

    return 0;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏腾讯云TStack专栏

《 大话 Ceph 》 之 PG 那点事儿

《大话 Ceph 》系列文章通过通俗易懂的语言并结合基础实验,用最简单的描述来讲解 Ceph 中的重要概念。让读者对分布式存储系统有一个清晰的理解。

2.3K30
来自专栏码洞

如何优雅的关闭Go Channel【译】

不要在消费端关闭channel,不要在有多个并行的生产者时对channel执行关闭操作。

29340
来自专栏源码之家

搞定博看原貌版杂志的下载

66130
来自专栏葡萄城控件技术团队

Asp.Net MVC4入门指南(7):给电影表和模型添加新字段

在本节中,您将使用Entity Framework Code First来实现模型类上的操作。从而使得这些操作和变更,可以应用到数据库中。 默认情况下,就像您在...

207100
来自专栏腾讯技术工程官方号的专栏

Ceph 集群整体迁移方案

本文就介绍了一种实现业务不中断的数据迁移方案,并已经在多个生产环境执行。

688120
来自专栏运维小白

1.3 认识Linux

1.3 认识Linux 1.认识linux linux是一个操作系统 andriod手机操作系统就是linux 2.linux起源 linux之前流行的系统是U...

21150
来自专栏皮振伟的专栏

[linux][memory]balloon技术分析

前言: 我大天朝人觉得什么东西含量不够,叫做有“水份”。内存的含量不足,叫“balloon”。作者是外语专业毕业的,感觉不同国度的人虽然语言不同,但是表达出来的...

57780
来自专栏拂晓风起

word 2007 不同章节插入不同样式的页码,不同的页眉

9920
来自专栏DeveWork

让WordPress 在RSS 中Feed 输出支持“More”标签

如果你的主题支持“more”标签,在写文章的时候加上“more”标签,首页就可以截断显示。“more”标签截断文章的意义在于能够随心所欲,想断就断(汗,越写越废...

21850
来自专栏沈唁志

WordPress秒变谷歌AMP加速移动页面并自动推送

25730

扫码关注云+社区

领取腾讯云代金券