BZOJ2242[SDOI2011]计算器——exgcd+BSGS

约定不等于承诺〃 2022-01-05 15:15 197阅读 0赞

## 题目描述 ##

你被要求设计一个计算器完成以下三项任务：

1、给定y,z,p,计算Y^Z Mod P 的值；

2、给定y,z,p，计算满足xy≡ Z ( mod P )的最小非负整数；

3、给定y,z,p，计算满足Y^x ≡ Z ( mod P)的最小非负整数。

## 输入 ##

输入包含多组数据。

第一行包含两个正整数T,K分别表示数据组数和询问类型（对于一个测试点内的所有数据，询问类型相同）。

以下行每行包含三个正整数y,z,p，描述一个询问。

## 输出 ##

对于每个询问，输出一行答案。对于询问类型2和3，如果不存在满足条件的，则输出“Orz, I cannot find x!”，注意逗号与“I”之间有一个空格。

## 样例输入 ##

【样例输入1】  
3 1  
2 1 3  
2 2 3  
2 3 3  
【样例输入2】  
3 2  
2 1 3  
2 2 3  
2 3 3  
【数据规模和约定】  
对于100%的数据，1<=y,z,p<=10^9，P为质数，1<=T<=10。

## 样例输出 ##

【样例输出1】  
2  
1  
2  
【样例输出2】  
2  
1  
0

数论模板题合集，第一问直接快速幂，第二问扩展欧几里得，第三问$BSGS$。

#include<set>
    #include<map>
    #include<queue>
    #include<stack>
    #include<cmath>
    #include<cstdio>
    #include<vector>
    #include<bitset>
    #include<cstring>
    #include<iostream>
    #include<algorithm>
    #define ll long long
    using namespace std;
    int T,k;
    ll y,z,p;
    ll G;
    map<ll,int>ind;
    ll quick(ll x,ll y,ll mod)
    {
    	ll res=1ll;
    	while(y)
    	{
    		if(y&1)
    		{
    			res=res*x%mod;
    		}
    		x=x*x%mod;
    		y>>=1;
    	}
    	return res;
    }
    ll gcd(ll x,ll y)
    {
    	return y==0?x:gcd(y,x%y);
    }
    void exgcd(ll x,ll y,ll &a,ll &b)
    {
    	if(!y)
    	{
    		a=1,b=0;
    		return ;
    	}
    	exgcd(y,x%y,b,a);
    	b-=(x/y)*a;
    }
    void solve(int opt)
    {
    	if(opt==1)
    	{
    		printf("%lld\n",quick(y,z,p));
    	}
    	else if(opt==2)
    	{
    		y%=p,z%=p;
    		ll d=gcd(y,p);
    		if(z%d)
    		{
    			printf("Orz, I cannot find x!\n");
    			return ;
    		}
    		y/=d,z/=d,p/=d;
    		ll a,b;
    		exgcd(y,p,a,b);
    		a*=z;
    		a=(a%p+p)%p;
    		printf("%lld\n",a);
    	}
    	else
    	{
    		ll n=ceil(sqrt(p));
    		if(y%p==0&&z)
    		{
    			printf("Orz, I cannot find x!\n");
    			return ;
    		}
    		ind.clear();
    		ll sum=z%p;
    		ind[sum]=0;
    		for(ll i=1;i<=n;i++)
    		{
    			sum=sum*y;
    			sum%=p;
    			ind[sum]=i;
    		}
    		sum=quick(y,n,p);
    		ll num=1ll;
    		for(int i=1;i<=n;i++)
    		{
    			num*=sum,num%=p;
    			if(ind.find(num)!=ind.end())
    			{
    				printf("%lld\n",((n*i-ind[num])%p+p)%p);
    				return ;
    			}
    		}
    		printf("Orz, I cannot find x!\n");
    	}
    }
    int main()
    {
    	scanf("%d%d",&T,&k);
    	while(T--)
    	{
    		scanf("%lld%lld%lld",&y,&z,&p);
    		solve(k);
    	}
    }

转载于:https://www.cnblogs.com/Khada-Jhin/p/10625384.html