登月计划
- 总时间限制:
- 40000ms
- 内存限制:
- 256000kB
- 描述
-
HJA在和学弟学数学,于是便有了一道非常简单的数学题:求满足 的最小自然数x。
- 输入
- 输入数据一行三个正整数a、b、p,我们保证p是一个质数。
- 输出
- 一行一个整数代表最小的自然数x,如果不存在这样的x输出-1。
- 样例输入
-
2 1 3
- 样例输出
-
0
- 提示
- 对于30%的数据,1≤p≤1000。
对于100%的数据,1≤a,b<p≤10^12。< dd=""> - 来源
- zhonghaoxi
BabyStepGiantStep
這道題考場上卡在了求解 a*x == b (mod p) 這一步上。
解a*x == b (mod p) 方法爲
a * b^(-1) * x == 1 (mod p)
x= (a*b^(-1))^(-1)
然而這樣還是要TLE,觀察發現其中每次求值時a總會乘上一個常數t,則x每次乘上t^(-1)就行了
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<ctime>
#include<cmath>
#include<algorithm>
#include<set>
#include<map>
#include<vector>
#include<string>
#include<queue>
using namespace std;
#ifdef WIN32
#define LL "%I64d"
#else
#define LL "%lld"
#endif
#define MAXN 1100000
#define MAXV MAXN*2
#define MAXE MAXV*2
#define INF 0x3f3f3f3f
#define INFL 0x3f3f3f3f3f3f3f3fLL
#define VAL1 1000007
#define PROB "braveheart"
typedef long long qword;
qword base,res,mod; struct Edge
{
qword t,v;
Edge *next;
}E[MAXE],*V[VAL1+];
int tope=-;
void addedge(int x,qword y,qword z)
{
E[++tope].t=y;
E[tope].v=z;
E[tope].next=V[x];
V[x]=&E[tope];
}
inline qword multi(qword x,qword y)
{
qword ret=;
if (y<)y=-y,x=-x;
while (y)
{
if (y&)ret=(ret+x)%mod;
x=(x+x)%mod;
y>>=;
}
return ret;
}
qword pow_mod(qword x,qword y,qword mod)
{
qword ret=;
while (y)
{
if (y&)ret=multi(ret,x);
x=multi(x,x);
y>>=;
}
return ret;
} int main()
{
freopen(PROB".in","r",stdin);
freopen(PROB".out","w",stdout);
int i;
qword x,y,z;
scanf(LL LL LL,&base,&res,&mod);
int sb=ceil(sqrt(mod-));
//baby step
x=;
for (i=;i<sb;i++)
{
addedge(x%VAL1,i,x);
x=multi(x,base);
}
qword val1;
val1=pow_mod(base,sb,mod);
qword a_i=;
Edge *ne;
bool flag=false;
qword t;
x=res%mod;
y=pow_mod(val1,mod-,mod);
for (i=;i<=sb;i++)
{
for (ne=V[x%VAL1];ne;ne=ne->next)
{
if (ne->v==x)
{
flag=true;
t=ne->t;
}
}
if (flag)
{
printf(LL "\n",(qword)i*sb+t);
return ;
}
x=multi(x,y);
}
printf("-1\n");
return ;
}
Contest 20140923 登月计划 BabyStepGaintStep的更多相关文章
-
阿波罗11号登月飞船电脑控制系统源码(AGC)
阿波罗11号登月飞船电脑控制系统源码(AGC) http://download.csdn.net/detail/downiis6/9574926 down url: https://github.co ...
-
2018年 7月总结&;8月计划
7月悄然而过... 英语: a打卡率:1号上课没有完成听力,7号上课没有完成阅读,21,22号考试 没有阅读 PS:学习效果测评 1)不要再阅读china English 2)单词要拼写 3)听力句子 ...
-
RQNOJ PID192 梦幻大PK [2017年6月计划 二分图02]
PID192 / 梦幻大PK ☆ 提交你的代码 查看讨论和题解 你还木有做过哦 我的状态 查看最后一次评测记录 质量 7 题目评价 质量 7 ★★★★★ ★★★★☆ ★★★☆☆ ★★☆ ...
-
HDU3078 Network [2016年6月计划 树上问题05]
Network Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)Total Sub ...
-
HDU3887 Counting Offspring [2017年6月计划 树上问题03]
Counting Offspring Time Limit: 15000/5000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Othe ...
-
洛谷P2912 [USACO08OCT]牧场散步Pasture Walking [2017年7月计划 树上问题 01]
P2912 [USACO08OCT]牧场散步Pasture Walking 题目描述 The N cows (2 <= N <= 1,000) conveniently numbered ...
-
Contest 20140923 潛行世界 拓撲排序,期望
潜行世界 查看 提交 统计 提问 总时间限制: 10000ms 内存限制: 256000kB 描述 HJA和学弟还在旅游中,这次他们来到了潜行世界.潜行世界是一个N个点M条边的有向无环图.每条路对 ...
-
洛谷P1368 均分纸牌(加强版) [2017年6月计划 数论14]
P1368 均分纸牌(加强版) 题目描述 有 N 堆纸牌,编号分别为 1,2,…, N.每堆上有若干张,纸牌总数必为 N 的倍数.可以在任一堆上取1张纸牌,然后移动. 移牌规则为:在编号为 1 堆上取 ...
-
洛谷P1621 集合 [2017年6月计划 数论13]
P1621 集合 题目描述 现在给你一些连续的整数,它们是从A到B的整数.一开始每个整数都属于各自的集合,然后你需要进行一下的操作: 每次选择两个属于不同集合的整数,如果这两个整数拥有大于等于P的公共 ...
随机推荐
-
【原】使用VirtIE6代替IE6
做前端开发难免要使用IE6,相信很多朋友知道win7上是不支持安装IE6的,通常会使用IETester,要么在win7中安装虚拟机,在虚拟机中安装IE6. 分析下这2种方式: IETester:并不是 ...
-
Android中关于Handler的若干思考
在之前的博文中,讲过一些和Handler有关的知识,例如: Android 多线程----AsyncTask异步任务详解 Android多线程----异步消息处理机制之Handler详解 今天再把Ha ...
-
重新想象 Windows 8 Store Apps (66) - 后台任务: 下载和上传
[源码下载] 重新想象 Windows 8 Store Apps (66) - 后台任务: 下载和上传 作者:webabcd 介绍重新想象 Windows 8 Store Apps 之 后台任务 后台 ...
-
php 小知识积累
1.如果能将类的方法定义成static,就尽量定义成static,它的速度会提升将近4倍. 2.$row['id']的速度是$row[id]的7倍. 3.echo比print快,并且使用echo的多重 ...
-
c语言指向结构体数组的指针
#include <stdio.h> #include <stdlib.h> struct dangdang { ]; ]; ]; int num; int bugnum; ] ...
-
TCP传输协议使用
TCP传输协议,也称之为套接字连接,比较安全,三次握手!,必须确保对方计算机存在,才能连接,而且是长时间连接. 缺点是传输速度有点慢. 你用 socket 去连接 ServiceSocaket 服务器 ...
-
python 循环语句 函数 模块
python循环语句 while循环语法结构 当需要语句不断的重复执行时,可以使用while循环 while expression: while_suite 语句ehile_suite会被连续不断的循 ...
-
Linux基础命令2
1.修改网络状态: 1).Cd /etc/sysconfig/network-scripts/network-scripts 2).vi ifcfg-eth0 编辑 onboot=yes: 3 ...
-
conda,pip 安装指定版本的指定包
1.conda 安装指定版本的指定包 cuda search tensorflow-gpu 有如下结果: 然后使用conda install package=version 就能安装指定版本的pack ...
-
C - The kth great number 优先队列
Xiao Ming and Xiao Bao are playing a simple Numbers game. In a round Xiao Ming can choose to write d ...