题解 P2485 【[SDOI2011]计算器】

xukuan · 2019-11-12 20:42:16 · 题解

这题其实有3种操作

1. 给定y、z、p，计算y^z \space mod \space p 的值

直接跑快速幂即可

2. 给定y、z、p，计算满足xy \equiv z(mod \space p)的最小非负整数x

转化一下，xy+pw=z。

二元一次不定方程，扩欧（exgcd）解决

3. 给定y、z、p，计算满足y^x \equiv z(mod \space p)的最小非负整数x，满足p是质数

直接跑是BSGS

不会BSGS的可以看这里：https://www.luogu.org/blog/xukuan/Baby-step-Gaint-step

代码：

#include<bits/stdc++.h>
#include<iostream>
#include<cstdio>
#define ll long long
using namespace std;

ll T,k;

inline ll read(){
    ll x=0,tmp=1;
    char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-') tmp=-1;
        ch=getchar();
    }
    while(isdigit(ch)){
        x=(x<<3)+(x<<1)+(ch^48);
        ch=getchar();
    }
    return tmp*x;
}

inline void write(ll x){
    if(x<0){
        putchar('-');
        x=-x;
    }
    ll y=10,len=1;
    while(y<=x){
        y=(y<<3)+(y<<1);
        len++;
    }
    while(len--){
        y/=10;
        putchar(x/y+48);
        x%=y;
    }
}

namespace solve1{
    ll n,m,mod;
    ll ksm(ll x,ll y){
        if(y==0) return 1;
        ll t=ksm(x,y>>1)%mod;
        t=t*t%mod;
        if(y&1) t=t*x%mod;
        return t;
    }
    inline void main(){
        while(T--){
            n=read(); m=read(); mod=read();
            write(ksm(n,m)); putchar('\n');
        }
    }
}

namespace solve2{
    ll n,m,mod;
    ll exgcd(ll a,ll b,ll &x,ll &y){
        if(!b){
            x=1; y=0;
            return a;
        }
        ll _gcd=exgcd(b,a%b,y,x);
        y-=a/b*x;
        return _gcd;
    }
    inline void main(){
        while(T--){
            n=read(); m=read(); mod=read();
            ll x,y;
            ll _gcd=exgcd(n,mod,x,y);
            if(m%_gcd) printf("Orz, I cannot find x!\n");
            else{
                ll g=mod/_gcd;
                while(x<0) x+=g;
                write(((x*m/_gcd)%mod+mod)%mod); putchar('\n');
            }
        }   
    }
}

namespace solve3{
    ll n,m,mod;
    map<ll,ll> mp;
    ll ksm(ll x,ll y){
        if(y==0) return 1;
        ll t=ksm(x,y>>1)%mod;
        t=t*t%mod;
        if(y&1) t=t*x%mod;
        return t;
    }
    inline void BSGS(ll x,ll y){
        mp.clear();
        if(y==1){
            printf("0\n");
            return;
        }
        ll m=sqrt(mod),s=y;
        for(ll i=0; i<=m; i++){
            mp[s]=i;
            s=s*x%mod;
        }
        ll xx=ksm(x,m); s=1;
        for(ll i=1; i<=m; i++){
            s=s*xx%mod;
            if(mp.count(s)){
                if(i*m-mp[s]==0) printf("Orz, I cannot find x!\n");
                else{write(i*m-mp[s]);putchar('\n');}
                return;
            }
        }
        printf("Orz, I cannot find x!\n");
    }
    inline void main(){
        while(T--){
            n=read(); m=read(); mod=read();
            if(n%mod) BSGS(n%mod,m%mod);
            else printf("Orz, I cannot find x!\n");
        }
    }
}

int main(){
    T=read(); k=read();
    switch(k){
        case 1:{
            solve1::main();
            break;
        }
        case 2:{
            solve2::main();
            break;
        }
        case 3:{
            solve3::main();
            break;
        }
    }
    return 0;
}