您现在的位置是:首页 > 正文

bzoj2242

2024-01-30 21:23:48阅读 0

2242: [SDOI2011]计算器

Time Limit: 10 Sec   Memory Limit: 512 MB
Submit: 3179   Solved: 1248
[ Submit][ Status][ Discuss]

Description

你被要求设计一个计算器完成以下三项任务:
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)的最小非负整数。

Input

 输入包含多组数据。

第一行包含两个正整数T,K分别表示数据组数和询问类型(对于一个测试点内的所有数据,询问类型相同)。
以下行每行包含三个正整数y,z,p,描述一个询问。

Output

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

Sample Input

【样例输入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,为质数,1<=T<=10。

Sample Output

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

HINT

Source

[ Submit][ Status][ Discuss]




这是一道题,也是3道题。。。前两道SB题,最后一道要求y^x=z(mod p)的x值

由于费马小定理,答案若存在一定不会>p-1

于是我们可以分块乱搞 

y^x=y^(k*sqrt(p)+i)=z (0<=i<sqrt(x))

即 y^i=z/(y^(k*sqrt(p))=z*inv(y^(k*sqrt(p)))=z*y^(k*sqrt(p)*(p-2)%(p-1))

哈希表乱搞即可

这个算法的学名叫大步小步算法--By mcfx


#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<tr1/unordered_map>
using namespace std;
tr1::unordered_map<int,int>st;
int qmod(int a,int b,int p){
	int tmp=a,ans=1;
	for(int i=0;b>>i;i++,tmp=1ll*tmp*tmp%p)
		if((b>>i)&1)ans=1ll*ans*tmp%p;
	return ans;
}
void exgcd(int a,int b,int& d,int &x,int &y){
	if(b==0){
		x=1;y=0;d=a;
	} else exgcd(b,a%b,d,y,x),y-=a/b*x;
}
int get(int y,int z,int p){
	int d,x,m;
//	printf("[%d,%d]",y,-p);
	exgcd(y,p,d,x,m);
	if(z%d!=0)return -1;
	while(x<0)x+=p;
	return 1ll*x*z%p;
}
int get2(int y,int z,int p){
	if(y%p==0)return z==0?1:-1;
	int mxs=sqrt(p)+1;
	int f=qmod(y,mxs,p);
	st.clear();
	for(int i=0,j=1;i<mxs;++i,j=1ll*j*y%p)
		if(!st.count(j))st[j]=i;
	for(int i=0;i<=p;i+=mxs){
		int ans=1ll*z*qmod(y,1ll*i*(p-2)%(p-1),p)%p;
		if(st.count(ans))return st[ans]+i;
	}
	return -1;
}
void print(int x){
	x==-1?printf("Orz, I cannot find x!\n"):printf("%d\n",x);
}
int main(){
	int y,z,p,t,k,x;
	scanf("%d%d",&t,&k);
	while(t--){
		scanf("%d%d%d",&y,&z,&p);
		if(k==1)printf("%d\n",qmod(y,z,p));
		else if(k==2)print(get(y,z,p));
		else if(k==3)print(get2(y,z,p));
	}
}



网站文章

  • JS逆向混淆加密参数分析,反调试分析

    JS逆向混淆加密参数分析,反调试分析

    闲逛github看到issues别人发的一个网站,网址:http://ys.fgj.taiyuan.gov.cn/Firsthand/tyfc/publish/p/ProjectList.do 随便勾选菜单查询,上抓包 如下图requestbody 分析一下requestbody的生成过程,老规矩F12 匿名函数的无限debugger,直接删掉debugger代码即可,有2个debugger...

    2024-01-30 21:23:40
  • 实现每日早安推送

    实现每日早安推送

    做一个程序员给女朋友的浪漫礼物吧,微信推送每日早安。

    2024-01-30 21:23:10
  • Linux环境下使用阿里云盘 热门推荐

    Linux环境下使用阿里云盘 热门推荐

    一直有个直播推流的想法,那就是把阿里云盘上的视频资源,在不下载到本地的情况下放在服务器上直播推流,这个时候就需要阿里云盘能能支持Linux环境下使用了。 目前阿里云盘官方还没有推出Linux环境下的版...

    2024-01-30 21:23:03
  • 软件测试常用的oracle语句,Oracle 一些常用的语句记录

    1、oracle数据库锁表查询:select db.object_name,sess.sid,sess.serial#,sess.module,sess.action ,'alter system k...

    2024-01-30 21:22:54
  • 本科阶段的一点总结

    先一点随笔大学转眼过去三年,这几年参加了各种比赛,硬件和软件也都做了一些,也靠这些和还算过得去的成绩拿到了保研名额,不过因为一些原因选择留在了本校直接攻读phd。。。 以后应该是学术向+技术向了,所以在这里开个坑,也算是对自己以后的学习的一个记录吧,主攻的方向该是机器学习和人工智能。 之后的博客也主要在这些方向上更新一些博文,或者有一些比较新颖的想法也会放上来和大家交流,决定读phd后感觉自己的

    2024-01-30 21:22:18
  • 【杂谈】网络修复杂谈

    前言断网,是仅次于断水、断电的危机,对于部分依赖于网络的人来说,可能重要性更加突出。这里主要谈一谈网络修复的方法与一些常见的故障。正题首先要知道怎么修复网络,就需要大致了解网络的运作方式,正如一个能够装机的人要会拆机、能够做网络防御的人要懂得网络攻击的原理。这里主要通过对几个名词的解析来大致描述网络的运作方式。由于这里只打算大致讲一下网络的工作方式,过多的说明可能比不上形象的比喻。

    2024-01-30 21:22:09
  • Linux与Windows共享文件、互传文件

    Linux与Windows共享文件、互传文件

    1.设置共享目录通过虚拟机,把一个windows目录共享,让linux可以访问这个目录2.复制文件夹

    2024-01-30 21:22:02
  • MySQL 事务

    在数据修改之前结果就可以被其他事务查看,不可以解决任何问题。

    2024-01-30 21:21:35
  • android后台如何获取客户端传来的值,Android:使用OkHttp框架与后台通讯、获取数据...

    android后台如何获取客户端传来的值,Android:使用OkHttp框架与后台通讯、获取数据...

    摘要:本文介绍了Android应用如何与服务器通讯的一些机制,并分享了笔者的一些开发经验与技巧,经过具体的代码描述OkHttp框架的使用,适合初学者。前端对于初学者来讲,先后端一手抓很常见,若是你想要...

    2024-01-30 21:21:16
  • 计算机主机板开机原理与维修,主机板损坏电脑会出现什么现象

    计算机主机板开机原理与维修,主机板损坏电脑会出现什么现象

    主机板损坏电脑会出现什么现象以下文字资料是由(历史新知网www.lishixinzhi.com)小编为大家搜集整理后发布的内容,让我们赶快一起来看一下吧!主机板损坏电脑会出现什么现象音效卡坏了不造成开...

    2024-01-30 21:21:08