BZOJ 2242: [SDOI2011]计算器( 快速幂 + 扩展欧几里德 + BSGS )

时间:2023-02-24 21:47:13

BZOJ 2242: [SDOI2011]计算器( 快速幂 + 扩展欧几里德 + BSGS )

没什么好说的...

---------------------------------------------------------------------

#include<cstdio>
#include<cmath>
#include<map>
 
using namespace std;
 
typedef long long ll;
 
int MOD;
 
void gcd(int a, int b, int& d, int& x, int& y) {
if(!b) {
d = a;
x = 1;
y = 0;
} else {
gcd(b, a % b, d, y, x);
y -= x * (a / b);
}
}
 
//x^t % MOD
int power(int x, int t) {
int ret = 1;
for(; t; t >>= 1) {
if(t & 1) ret = ll(x) * ret % MOD;
x = ll(x) * x % MOD;
}
return ret;
}
 
//a^x = b(mod MOD)
int BSGS(int a, int b) {
if(a % MOD == 0) return -1;
int m = sqrt(MOD + 0.5), e = 1, v = power(a, MOD - m - 1);
map<int, int> x;
x[1] = 0;
for(int i = 1; i < m; i++) {
e = ll(e) * a % MOD;
if(!x.count(e)) x[e] = i;
}
for(int i = 0; i < m; i++) {
if(x.count(b)) return i * m + x[b];
b = ll(b) * v % MOD;
}
return -1;
}
 
int main() {
int T, K; scanf("%d%d", &T, &K);
while(T--) {
int a, b;
scanf("%d%d%d", &a, &b, &MOD);
if(K == 1)
   printf("%d\n", power(a, b));
else if(K == 2) {
int d, x, y;
gcd(a, MOD, d, x, y);
if(b % d != 0) puts("Orz, I cannot find x!");
else
printf("%d\n", (int) ((ll(x) * b / d % MOD + MOD) % MOD));
} else if(K == 3) {
int t = BSGS(a, b);
if(~t) printf("%d\n", t);
else 
   puts("Orz, I cannot find x!");
}
}
return 0;
}

---------------------------------------------------------------------

2242: [SDOI2011]计算器

Time Limit: 10 Sec  Memory Limit: 512 MB
Submit: 2111  Solved: 825
[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

BZOJ 2242: [SDOI2011]计算器( 快速幂 + 扩展欧几里德 + BSGS )的更多相关文章

  1. bzoj 2242 &lbrack;SDOI2011&rsqb;计算器 快速幂&plus;扩展欧几里得&plus;BSGS

    1:快速幂  2:exgcd  3:exbsgs,题里说是素数,但我打的普通bsgs就wa,exbsgs就A了...... (map就是慢)..... #include<cstdio> # ...

  2. BZOJ 2242&colon; &lbrack;SDOI2011&rsqb;计算器 &lbrack;快速幂 BSGS&rsqb;

    2242: [SDOI2011]计算器 题意:求\(a^b \mod p,\ ax \equiv b \mod p,\ a^x \equiv b \mod p\),p是质数 这种裸题我竟然WA了好多次 ...

  3. BZOJ&lowbar;2242&lowbar;&lbrack;SDOI2011&rsqb;计算器&lowbar;快速幂&plus;扩展GCD&plus;BSGS

    BZOJ_2242_[SDOI2011]计算器_快速幂+扩展GCD+BSGS 题意: 你被要求设计一个计算器完成以下三项任务: 1.给定y,z,p,计算Y^Z Mod P 的值: 2.给定y,z,p, ...

  4. bzoj 2242&colon; &lbrack;SDOI2011&rsqb;计算器 BSGS&plus;快速幂&plus;扩展欧几里德

    2242: [SDOI2011]计算器 Time Limit: 10 Sec  Memory Limit: 512 MB[Submit][Status][Discuss] Description 你被 ...

  5. bzoj 2242&colon; &lbrack;SDOI2011&rsqb;计算器【扩展欧几里得&plus;快速幂&plus;BSGS】

    第一问快速幂板子 第二问把式子转化为\( xy\equiv Z(mod P)\rightarrow xy+bP=z \),然后扩展欧几里得 第三问BSGS板子 #include<iostream ...

  6. BZOJ 2242 &lbrack;SDOI2011&rsqb;计算器(快速幂&plus;Exgcd&plus;BSGS)

    [题目链接] http://www.lydsy.com/JudgeOnline/problem.php?id=2242 [题目大意] 给出T和K 对于K=1,计算 Y^Z Mod P 的值 对于K=2 ...

  7. BZOJ 2242 &lbrack;SDOI2011&rsqb;计算器 ——EXGCD&sol;快速幂&sol;BSGS

    三合一的题目. exgcd不解释,快速幂不解释. BSGS采用了一种不用写EXGCD的方法,写起来感觉好了很多. 比较坑,没给BSGS的样例(LAJI) #include <map> #i ...

  8. BZOJ&period;2242&period;&lbrack;SDOI2011&rsqb;计算器&lpar;扩展欧几里得 BSGS&rpar;

    同余方程都不会写了..还一直爆int /* 2.关于同余方程ax ≡b(mod p),可以用Exgcd做,但注意到p为质数,y一定有逆元 首先a%p=0时 仅当b=0时有解:然后有x ≡b*a^-1( ...

  9. BZOJ 2242 &lbrack;SDOI2011&rsqb;计算器 BSGS&plus;高速幂&plus;EXGCD

    题意:id=2242">链接 方法: BSGS+高速幂+EXGCD 解析: BSGS- 题解同上.. 代码: #include <cmath> #include <c ...

随机推荐

  1. OpenMP编程总结表

    本文对OpenMP 2.0的全部语法——Macro(宏定义).Environment Variables(环境变量).Data Types(数据类型).Compiler Directives(编译指导 ...

  2. 关于Jquery中ajax介绍

    jQuery 底层 AJAX 实现.简单易用的高层实现见 $.get, $.post 等.$.ajax() 返回其创建的 XMLHttpRequest 对象.大多数情况下你无需直接操作该函数,除非你需 ...

  3. 【poj1741】 Tree

    http://poj.org/problem?id=1741 (题目链接) 题意 给出一个n个节点的带权树,求树上距离不超过K的所有点对的个数. solution  点分治裸题.所谓的点分治,就是对于 ...

  4. ASP&period;NET MVC中错误日志信息记录

    MVC中有一个处理异常的过滤器 HandleErrorAttribute 1.新建一个类继承自 HandleErrorAttribute,然后重写OnException这个方法 public clas ...

  5. Android 时间轴TimeLine

    代码:这里

  6. Maximum Subarray &sol; Best Time To Buy And Sell Stock 与 prefixNum

    这两个系列的题目其实是同一套题,可以互相转换. 首先我们定义一个数组: prefixSum (前序和数组) Given nums: [1, 2, -2, 3] prefixSum: [0, 1, 3, ...

  7. kafka快速入门

    一.kafka简介 kafka,ActiveMQ,RabbitMQ是当今最流行的分布式消息中间件,其中kafka在性能及吞吐量方面是三者中的佼佼者,不过最近查阅官网时,官方与它的定义为一个分布式流媒体 ...

  8. &period;NET framework访问Oracle的几种方法

    首先介绍下开发环境:WIn10 64bit+Visual Studio 2015+Oracle10ClientWin32(只是客户端,如果安装整个数据库也是可以的) 目前了解C#中连接Oracle数据 ...

  9. 【深入Java虚拟机】二 类加载与双亲委派

    https://blog.csdn.net/zhangliangzi/article/details/51338291  -参考 双亲委派过程:当一个类加载器收到类加载任务时,立即将任务委派给它的父类 ...

  10. Fiddler抓包9-保存会话(save)

    前言 为什么要保存会话呢?举个很简单的场景,你在上海测试某个功能接口的时候,发现了一个BUG,而开发这个接口的开发人员是北京的一家合作公司.你这时候给对方开发提bug, 如何显得专业一点,能让对方心服 ...