Contest 20140923 登月计划 BabyStepGaintStep

时间:2022-11-01 00:16:07

登月计划

总时间限制: 
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的更多相关文章

  1. 阿波罗11号登月飞船电脑控制系统源码(AGC)

    阿波罗11号登月飞船电脑控制系统源码(AGC) http://download.csdn.net/detail/downiis6/9574926 down url: https://github.co ...

  2. 2018年 7月总结&amp&semi;8月计划

    7月悄然而过... 英语: a打卡率:1号上课没有完成听力,7号上课没有完成阅读,21,22号考试 没有阅读 PS:学习效果测评 1)不要再阅读china English 2)单词要拼写 3)听力句子 ...

  3. RQNOJ PID192 梦幻大PK &lbrack;2017年6月计划 二分图02&rsqb;

    PID192 / 梦幻大PK ☆ 提交你的代码 查看讨论和题解 你还木有做过哦 我的状态         查看最后一次评测记录 质量 7 题目评价 质量 7 ★★★★★ ★★★★☆ ★★★☆☆ ★★☆ ...

  4. HDU3078 Network &lbrack;2016年6月计划 树上问题05&rsqb;

    Network Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)Total Sub ...

  5. HDU3887 Counting Offspring &lbrack;2017年6月计划 树上问题03&rsqb;

    Counting Offspring Time Limit: 15000/5000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Othe ...

  6. 洛谷P2912 &lbrack;USACO08OCT&rsqb;牧场散步Pasture Walking &lbrack;2017年7月计划 树上问题 01&rsqb;

    P2912 [USACO08OCT]牧场散步Pasture Walking 题目描述 The N cows (2 <= N <= 1,000) conveniently numbered ...

  7. Contest 20140923 潛行世界 拓撲排序,期望

    潜行世界 查看 提交 统计 提问 总时间限制:  10000ms 内存限制:  256000kB 描述 HJA和学弟还在旅游中,这次他们来到了潜行世界.潜行世界是一个N个点M条边的有向无环图.每条路对 ...

  8. 洛谷P1368 均分纸牌(加强版) &lbrack;2017年6月计划 数论14&rsqb;

    P1368 均分纸牌(加强版) 题目描述 有 N 堆纸牌,编号分别为 1,2,…, N.每堆上有若干张,纸牌总数必为 N 的倍数.可以在任一堆上取1张纸牌,然后移动. 移牌规则为:在编号为 1 堆上取 ...

  9. 洛谷P1621 集合 &lbrack;2017年6月计划 数论13&rsqb;

    P1621 集合 题目描述 现在给你一些连续的整数,它们是从A到B的整数.一开始每个整数都属于各自的集合,然后你需要进行一下的操作: 每次选择两个属于不同集合的整数,如果这两个整数拥有大于等于P的公共 ...

随机推荐

  1. 【原】使用VirtIE6代替IE6

    做前端开发难免要使用IE6,相信很多朋友知道win7上是不支持安装IE6的,通常会使用IETester,要么在win7中安装虚拟机,在虚拟机中安装IE6. 分析下这2种方式: IETester:并不是 ...

  2. Android中关于Handler的若干思考

    在之前的博文中,讲过一些和Handler有关的知识,例如: Android 多线程----AsyncTask异步任务详解 Android多线程----异步消息处理机制之Handler详解 今天再把Ha ...

  3. 重新想象 Windows 8 Store Apps &lpar;66&rpar; - 后台任务&colon; 下载和上传

    [源码下载] 重新想象 Windows 8 Store Apps (66) - 后台任务: 下载和上传 作者:webabcd 介绍重新想象 Windows 8 Store Apps 之 后台任务 后台 ...

  4. php 小知识积累

    1.如果能将类的方法定义成static,就尽量定义成static,它的速度会提升将近4倍. 2.$row['id']的速度是$row[id]的7倍. 3.echo比print快,并且使用echo的多重 ...

  5. c语言指向结构体数组的指针

    #include <stdio.h> #include <stdlib.h> struct dangdang { ]; ]; ]; int num; int bugnum; ] ...

  6. TCP传输协议使用

    TCP传输协议,也称之为套接字连接,比较安全,三次握手!,必须确保对方计算机存在,才能连接,而且是长时间连接. 缺点是传输速度有点慢. 你用 socket 去连接 ServiceSocaket 服务器 ...

  7. python 循环语句 函数 模块

    python循环语句 while循环语法结构 当需要语句不断的重复执行时,可以使用while循环 while expression: while_suite 语句ehile_suite会被连续不断的循 ...

  8. Linux基础命令2

    1.修改网络状态: 1).Cd  /etc/sysconfig/network-scripts/network-scripts 2).vi ifcfg-eth0   编辑  onboot=yes: 3 ...

  9. conda,pip 安装指定版本的指定包

    1.conda 安装指定版本的指定包 cuda search tensorflow-gpu 有如下结果: 然后使用conda install package=version 就能安装指定版本的pack ...

  10. 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 ...