Discrete Roots

题目描述

题解

首先考虑非余数情况下
\(x^k=A \rightarrow ln(x^k)=lnA \rightarrow x=e^{\frac{lnA}{k}}=A^{\frac{1}{k}}\)

在余数下，ln可以转换为ind指标形式
则
\(k\cdot ind(x)\equiv ind(A) \: \:(mod\:\: P-1)\)
求出ind(A)后上式就是一个一元一次模方程组\(k\cdot x+(P-1)\cdot y=ind(A)\)
用exgcd即可求出ind(x),成立当且仅当(k,P-1)| ind(A)
求出特解x，现在要求的所有的解，我们可以通过不断的向上调整 ?? 来得到所有的 ??，
因为\(0\leq x \leq P-1\)，所以x在向上调整过程中模P-1是有周期的，用map记录下就行
最后\(x\equiv g^{ind(x)} (mod \: P)\)

所以本题分为三步
首先求出P意义下的原根g
再用BSGS求ind(A)
用exgcd求出ind(x)
最后再求出x

点击查看代码 
 #include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long 
using namespace std;
const int maxn=1e6+10101;
const int MOD=998244353;
const int inf=2147483647;
const double pi=acos(-1);
ll read(){
    ll x=0,f=1;char ch=getchar();
    for(;!isdigit(ch);ch=getchar())if(ch=='-')f=-1;
    for(;isdigit(ch);ch=getchar())x=x*10+ch-'0';
    return x*f;
}
ll power(ll x,ll y,ll mod){
    ll ans=1;
    while(y){
        if(y&1)ans=ans*x%mod;
        y>>=1;x=x*x%mod;
    }
    return ans;
}
void exgcd(ll a,ll b,ll &d,ll &x,ll &y){
    if(!b){d=a;x=1ll;y=0ll;return;}
    exgcd(b,a%b,d,x,y);
    ll t=x;x=y;y=t-(a/b)*y;
    return ;
}
ll BSGS(ll g,ll x,ll p){
    if(x==1)return 0;
    ll B=sqrt(p)+1;
    mapji;
    for(ll b=0,t=x;b<=B;b++,t=t*g%p)ji[t]=b;
    for(ll a=1,t=power(g,B,p),tt=t;a<=B;a++,tt=t*tt%p){
        if(ji[tt])return a*B-ji[tt];
    }
    return 0;
}
vector cal(ll k,ll phi,ll t){
    vectorans;
    ll x,y,d;
    exgcd(k,phi,d,x,y);
    if(t%d)return ans;
    ll now=phi/d;
    x=(x*(t/d)%now+now)%now;
    mapji;
    for(int i=0;izhi;
    for(ll i=2;i*i<=phi;i++){
        if(phi%i==0){
            zhi.push_back(i);
            while(phi%i==0)phi/=i;
        }
    }
    if(phi>1)zhi.push_back(phi);
    for(int i=1;i
刷题

相关

2017 清北济南考前刷题Day 6 morning

面试随缘刷题--day7

C语言刷题笔记6

LeetCode刷题总结-数组篇（上）

C语言刷题笔记5

C语言刷题笔记4

[整理]qbxt周末刷题班 Day2总结

刷题记录——疫情问答积分（模拟）

Leetcode 刷题小抄 Java版

LeetCode刷题之DP算法

力扣每天刷题(2)

free code camp 刷题记录 js(ES6 箭头函数)

标签