首页 > 其他分享 >9.【题解】计算器

9.【题解】计算器

时间:2024-01-30 10:59:44浏览次数:41  
标签:return gcd int 题解 计算器 long large ans

题解

\(BSGS\)(拔山盖世)

  • 其实叫 \(Baby\) \(Step\) \(Giant\) \(Step\) (大步小步)\(qwq\) ,事实上还有 \(ex\) \(BSGS\) ,但是这里只写 \(BSGS\) 。
  • 当 \(\gcd(x,y)=1\) 时, \(BSGS\) 可以用 \(\sqrt n\) 的时间复杂度求解 \(\large y^x\equiv z\pmod z\) 的问题。(原根是 \(\large x^a\equiv z\pmod p\) )
  • 基本的思路就是,设 \(x=am-b\) ,其中 \(m=\lceil\sqrt p\rceil\) , \(b<m\) ,得出 \(\large y^{am-b}\equiv z\pmod p\) 继续得出 \(\large y^{am}\equiv zy^b\pmod p\) 。
  • 用哈希或 \(map\) 存下 \(zy^b\) 的所有值,再枚举 \(y^{am}\) 是否可以与 \(zy^b\) 的值相等。显然,如果有数可以满足,就是有解的,否则无解。
  • map复杂度 \(O(\sqrt n\log n)\) ,哈希复杂度 \(O(\sqrt n)\) 。

题解

  • \(t=1\) 和 \(t=2\) 的情况很好判断,\(t=1\) 时写一个快速幂就好了, \(t=2\) 时也不难,用 \(exgcd\) 。首先 \(\large xy\equiv z\pmod P\) , 于是很容易得出 \(\large xy+iP=Z+jp\) 。所以 \(\large xy+(i-j)P=Z\) 。很明显你也看出来了, \(\large ax+by=\gcd(a,b)\) 。因为这里 \(P\) 是个质数,所以可以把 \(\gcd(a,b)\) 看成 \(1\) 。 之后就将 \(x,y\) 扩大 \(Z\) 倍,就得到了 \(\large ax+by=Z\) 。再找出最小非负整数解即可。
  • \(t=3\) 直接套 \(BSGS\) 。

代码

#include<bits/stdc++.h>
#define N (10000010)
#define int long long
using namespace std;
namespace IO
{
    #define ll long long
    const int MAX=1<<25;
    char buf[MAX],*p1=buf,*p2=buf;
    char obuf[MAX],*o=obuf;
    #define gc()(p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)
    //template<typename T>
    //inline T read()
    inline int read()
    {
        int x=0;bool f=1;
        char c=gc();
        for(;c<48||c>57;c=gc())if(c=='-')f=0;
        for(;c>=48&&c<=57;c=gc())x=(x<<3)+(x<<1)+(c^48);
        return f?x:~x+1;
    }
    void print(ll x){if(x>9)print(x/10);*o++=(x%10)+'0';}
    void pit(ll x){if(x<0)*o++='-',x=~x+1;print(x);}
    void write(ll x,char end){pit(x);*o++=end;}
    void flush(){fwrite(obuf,o-obuf,1,stdout);}
    #undef ll
}
using IO::read;using IO::write;using IO::flush;
int n,m,t,P,q,d;
int x,y,k,ans,possible,lon;
int mod[N],a[N],gt[N],nth_mod[N];
int len,prime[700010],phi[N];//线性筛欧拉函数
short mu[N];
int mtot;
bitset<N>vis;
int jc[N];
long long inv[N];//乘法逆元
inline int max(int x,int y){return x>y?x:y;}
inline int min(int x,int y){return x<y?x:y;}
inline void swap(int &x,int &y){int tmp=x;x=y;y=tmp;}
int e[N],siz[N];
long long qpow(long long x,int b,int P=P)
{
    long long ans=1;
    for(;b;b>>=1){if(b&1)ans=(ans*x)%P;x=(x*x)%P;}
    return ans;
}//O(log(b))
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int exgcd(int a,int b,int &x,int &y)
{
    if(!b){x=1,y=0;return a;}
    int d=exgcd(b,a%b,y,x);
    y-=(a/b*x);
    return d;
}//O(max(a,b))
int ola(int n)
{
    int ans=n;
    for(int i=2;i*i<=n;++i)
    {
        if(n%i==0)ans=ans/i*(i-1);
        for(;n%i==0;n/=i);
    }
    if(n>1)ans=ans/n*(n-1);
    return ans;
}//O(sqrt(n))
void eular(int n)//欧拉筛
{
    //memset(vis,0,sizeof(vis));
    phi[1]=1;
    for(int i(2);i<=n;++i)
    {
        if(!vis[i])
            prime[++len]=i,phi[i]=(i-1);
        for(int j(1);j<=len&&i*prime[j]<=n;++j)
        {
            vis[i*prime[j]]=1;
            if(!(i%prime[j]))
                {phi[i*prime[j]]=(phi[i]*prime[j]);break;}
            else phi[i*prime[j]]=(phi[i]*(prime[j]-1));
        }
    }
}//O(n)
void mobius(int n)
{
    //memset(vis,0,sizeof(vis));
    mu[1]=1;
    for(int i(2);i<=n;++i)
    {
        if(!vis[i])prime[++mtot]=i,mu[i]=-1;
        for(int j(1);j<=mtot&&i*prime[j]<=n;++j)
        {
            vis[i*prime[j]]=1;
            if(!(i%prime[j])){mu[i*prime[j]]=0;break;}
            mu[i*prime[j]]=~mu[i]+1;
        }
    }
}//O(n)
void eular_mobius(int n)
{
    //memset(vis,0,sizeof(vis));
    mu[1]=phi[1]=1;
    for(int i(2);i<=n;++i)
    {
        if(!vis[i])prime[++len]=i,phi[i]=(i-1),mu[i]=-1;
        for(int j(1);j<=len&&i*prime[j]<=n;++j)
        {
            vis[i*prime[j]]=1;
            if(!(i%prime[j]))
            {
                phi[i*prime[j]]=(phi[i]*prime[j]);
                mu[i*prime[j]]=0;
                break;
            }
            phi[i*prime[j]]=(phi[i]*(prime[j]-1));
            mu[i*prime[j]]=~mu[i]+1;
        }
    }
}
void niyuan1(int n,int P=P)//乘法逆元
{
    inv[1]=1;
    for(int i(2);i<=n;++i)inv[i]=((P-P/i)*inv[P%i])%P;
}//O(n)
int inv_it(int a,int P=P)//O(log(a))
{
    int d(exgcd(a,P,x,y));
    return(x%P+P)%P;
}
int C(int n,int m,int P=P)
{
    if(m>n)return 0;
    int a(1),b(1);
    for(int i(n-m+1);i<=n;++i)a=(a*i)%P;
    for(int i(2);i<=m;++i)b=(b*i)%P;
    return(a*qpow(b,P-2,P))%P;
}
int lucas(int n,int m,int P=P)
{return(!m)?1:(C(n%P,m%P,P)*lucas(n/P,m/P,P))%P;}
int excrt(int n)//扩展中国剩余定理
{
    int mul(mod[1]);ans=a[1];
    int x,y,c,d;
    for(int i(2);i<=n;++i)
    {
        x=y=0;
        c=(a[i]-ans%mod[i]+mod[i])%mod[i];
        d=exgcd(mul,mod[i],x,y);
        if(!(c%d))
            ans+=(((x+mod[i])%mod[i])*(c/d)%mod[i])*mul,
            mul=mul*mod[i]/gcd(mul,mod[i]),
            ans%=mul;
        else return -1;
    }
    return ans%mul;
}
int exlucas_jc(int n,int mod,int P=P)
{
    if(!n)return 1;
    int res(1);
    for(int i(1);i<=P;++i)//不含因子mod[now]
        if(i%mod)res=(res*i)%P;
    res=qpow(res,n/P,P);
    for(int i(1);i<=n%P;++i)if(i%mod)res=(res*i)%P;
    return(res*(exlucas_jc(n/mod,mod,P)))%P;
}
int cal(int n,int m,int mod,int P=P)
{
    int c1(exlucas_jc(n,mod,P));
    int c2(exlucas_jc(m,mod,P));
    int c3(exlucas_jc(n-m,mod,P));
    int cnt(0);
    for(int i(n);i;i/=mod)cnt+=(i/mod);
    for(int i(m);i;i/=mod)cnt-=(i/mod);
    for(int i(n-m);i;i/=mod)cnt-=(i/mod);
    return(((qpow(mod,cnt,P)*c1)%P*inv_it(c2,P))%P*inv_it(c3,P))%P;
}
inline int crt(int x,int mod,int P)
{
    return inv_it(P/mod,mod)*(P/mod)*x;
}
int exlucas(int n,int m,int now,int P)
{return(crt(cal(n,m,nth_mod[now],mod[now]),mod[now],P));}
namespace hs
{
    int nhs,mhs,hs[100010],to[100010],nxt[100010];
    int mod=98317,head[100010],cnmhs;
    void clean(){memset(head,0,sizeof(head));}
    void add(int x,int P=mod)
    {
        hs[++cnmhs]=x,to[cnmhs]=P,x%=mod,
        nxt[cnmhs]=head[x],head[x]=cnmhs;
    }
    int find_x(int x)
    {
        for(int i(head[x%mod]);i;i=nxt[i])
            if(hs[i]==x)return to[i];
        return -1;
    }
}
using namespace hs;
int bsgs(int x,int y,int P=P)
{
    if(!(x%P))return -1;
    x%=P,y%=P;
    if(y==1)return 0;
    int Z(sqrt(P)+1);
    int xx(y),yy;
    hs::clean();
    for(int i(0);i<Z;++i,xx=(xx*x)%P)hs::add(xx,i);
    yy=qpow(x,Z),xx=1;
    for(int i(1),k;i<=Z;++i)
    {
        xx=(xx*yy)%P,k=hs::find_x(xx);
        if(k!=-1)return i*Z-k;
    }
    return -1;
}
signed main()
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    m=read(),t=read();
    int sum(0),num(0);ans=1;
    if(t==1)
        for(int i(1);i<=m;++i)
        {
            n=read(),q=read(),P=read();
            cout<<qpow(n,q,P)<<'\n';
        }
    else if(t==2)
        for(int i(1);i<=m;++i)
        {
            n=read(),q=read(),P=read();
            d=exgcd(n,P,x,y);
            if(q%d)cout<<"Orz, I cannot find x!\n";
            else x*=q/d,y=P/d,cout<<(x%y+y)%y<<'\n';
        }
    else
        for(int i(1);i<=m;++i)
        {
            n=read(),q=read(),P=read();
            d=bsgs(n%P,q%P,P);
            if(d<0)cout<<"Orz, I cannot find x!\n";
            else cout<<d<<'\n';
        }
    flush();
    return 0;
}

标签:return,gcd,int,题解,计算器,long,large,ans
From: https://www.cnblogs.com/minecraft666/p/17971188

相关文章

  • P6824 「EZEC-4」可乐 题解
    题目链接:可乐一开始想着0-1Trie,枚举\(x\)去写,然后判断就行了。然后想起南京区域赛的C题,其实和这个也有点大同小异的感觉,可以用更朴素的办法,找到对于一个\(a_i\)而言,满足题意的所有\(x\)去\(+1\)。这玩意很容易办到的,稍微讨论下:类似0-1Trie的按位讨论,从高位开始,我......
  • [ARC163D] Sum of SCC 题解
    题目链接点击打开链接题目解法好牛的性质!!!首先一个家喻户晓的性质是:竞赛图缩点之后是一条链考虑从这个上面拓展出一个更优美的性质:竞赛图的\(scc\)个数\(=\)把点集分成两个集合\(A,B\),满足\(\forallu\inA,v\inB\),\(u,v\)之间边的方向为\(u\tov\)的方案数\(-1\)......
  • CF1925B A Balanced Problemset? 题解
    CF1925B题解题目链接CodeforcesLuogu题目大意有一个长度为\(n\)且和为\(x\)的正整数序列,询问该序列可能的最大公因数。多测。简要思路首先先给出结论:最终的答案一定是\(x\)的因数。接下来我通过两种方法证明:一、类似于“更相减损法”一个序列的\(\gcd\)等于......
  • 2024 USACO 题解
    BronzeSilverT1Question给你长度为\(n\)的序列\(c\),$0\lec_i\leC$。若当前位置为\(0\)则表示这个数未知,要求你填数使得序列字典序最小,并满足给出的\(q\)条限制\((a_j,h_j)\),使得\(C_{h_j}\)是第一个严格大于\(C_1\cdotsC_{a_j}\)的数。Solution我的方法叫......
  • CF1925D Good Trip 题解
    考虑分别计算\(p\)和\(q\)。按照期望的定义,\(q\)应该等于方案的总数,也就是\(s^k\),其中\(s\)表示一共有多少个不同的组。考虑如何求\(p\),我们先只计算第\(i\)组对\(p\)的贡献。如果第\(i\)组一共被选了\(1\)次,那么贡献为:\[g=f_i\timesC_{k}^{1}\times(s-1)^{......
  • P5208 [WC2019] I 君的商店 题解
    第一道黑题,发个题解。很好玩的一道交互题。题意有一个长为\(n\)的01字符串,保证至少有一个1,且已知1的数量的奇偶性。每次可以询问两个下标集合,返回哪个下标集合中1的个数更多(相同则可能返回其中任意的一个)。求该字符串,查询次数有限。题解我们约定a,b,c等......
  • 洛谷题解-[ABC286E] Souvenir
    https://www.luogu.com.cn/problem/AT_abc286_e题目描述NNN個の都市があり、いくつかの相異なる都市の間は一方通行の直行便によって移動することができます。どの直行便が存在するかはNNN個の長さNNNの文字列S1,S2,…,SNS_1,S_2,\ldots,S_NS1​,S2​,…,SN​......
  • P5208 [WC2019] I 君的商店 题解
    第一道黑题,发个题解。很好玩的一道交互题。题意有一个长为\(n\)的01字符串,保证至少有一个1,且已知1的数量的奇偶性。每次可以询问两个下标集合,返回哪个下标集合中1的个数更多(相同则可能返回其中任意的一个)。求该字符串,查询次数有限。题解我们约定a,b,c等......
  • 题解 [ABC338D] Island Tour
    【洛谷博客】被降智的一道简单题。题意\(n\)个岛屿,第\(i\)座桥连接\(i\)和\(i+1\)(第\(N\)座桥连接着\(1\)和\(N\))。有一条长度为\(M\)的旅游序列\(X\),你需要按照顺序依次经过这些点,选择断掉一座桥使得旅游经过的桥最少。分析设断掉第\(i\)座桥会因为绕行增......
  • P10114 [LMXOI Round 1] Size 题解
    题目链接:[LMXOIRound1]Size挺有意思的诈骗题,其实这类题都喜欢批一个外壳,例如数据范围提示之类的。记得以前遇到的很多诈骗题,有一道cf的高分题,问的是区间出现次数的次数\(mex\),这玩意一开始感觉好难,出现次数还简单,还要考虑次数的次数,所以带修莫队的时候,一直没法确定怎么解决......