NC20347. [SDOI2011]计算器
描述
输入描述
输入包含多组数据。
第一行包含两个正整数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 1 2
示例2
输入:
3 2 2 1 3 2 2 3 2 3 3
输出:
2 1 0
C++14(g++5.4) 解法, 执行用时: 142ms, 内存消耗: 2020K, 提交时间: 2019-10-13 16:11:48
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int T,k;
ll x,y,z,p;
ll qpow(ll a,ll n,ll p)
{
ll res=1;
while(n)
{
if(n&1) res=res*a%p;
a=a*a%p;
n>>=1;
}
return res;
}
void solve1()
{
printf("%lld\n",qpow(y,z,p));
}
void solve2()
{
if((y%p)==0)
{
printf("Orz, I cannot find x!\n");
return;
}
ll g=qpow(y,p-2,p);
printf("%lld\n",g*z%p);
}
void solve3()
{
if((y%p)==0)
{
printf("Orz, I cannot find x!\n");
return;
}
int m,v,e=z;
m=(int)sqrt(1.0*p)+1;
map<int,int>g;
v=qpow(y,m,p);
for(int i=0;i<m;i++,e=1ll*e*y%p) g[e]=i;
e=1;
for(int i=0;i<=m;++i,e=1ll*e*v% p)
if(g.count(e)&& m*i-g[e]>=0) {printf("%d\n",m*i-g[e]);return;}
printf("Orz, I cannot find x!\n");
return;
}
int main()
{
scanf("%d%d",&T,&k);
while(T--)
{
scanf("%lld%lld%lld",&y,&z,&p);
if(k==1) solve1();
else if(k==2) solve2();
else if(k==3) solve3();
}
return 0;
}