什么叫高次同余方程?说白了就是解决这样一个问题: A^x=B(mod C),求最小的x值. baby step giant step算法 题目条件:C是素数(事实上,A与C互质就可以.为什么?在BSGS算法中是要求a^m在%c条件下的逆元的,如果a.c不互质根本就没有逆元.) 如果x有解,那么0<=x<C,为什么? 我们可以回忆一下欧拉定理: 对于c是素数的情况,φ(c)=c-1 那么既然我们知道a^0=1,a^φ(c)=1(在%c的条件下).那么0~φ(c)必定是一个循环节(不一定是最小的)

1038 X^A Mod P 基准时间限制:1 秒 空间限制:131072 KB 分值: 320 X^A mod P = B,其中P为质数.给出P和A B,求< P的所有X. 例如:P = 11,A = 3,B = 5. 3^3 Mod 11 = 5 所有数据中,解的数量不超过Sqrt(P).   Input 第1行:一个数T,表示后面用作输入测试的数的数量.(1 <= T <= 100) 第2 - T + 1行:每行3个数P A B,中间用空格隔开.(1 <= A, B <

高次同余方程 一般来说,高次同余方程分\(a^x \equiv b(mod\ p)\)和\(x^a \equiv b(mod\ p)\)两种,其中后者的难度较大,本片博客仅将介绍第一类方程的解决方法. 给定\(a,b,p\),其中\(gcd(a,p)=1\),求方程\(a^x \equiv b(mod\ p)\)的最小非负整数解. 普通分析和朴素算法 先介绍一下欧拉定理: 如果正整数\(a\),\(p\)互质,则\(a^{\phi(p)}\equiv1(mod\ p)\). 注意到题中所给的条件

/*poj 3243 *解决高次同余方程的应用,已知 X^Y = K mod Z, 及X,Z,K的值,求 Y 的值 */ #include<cstdio> #include<cstring> #include<cmath> using namespace std; #define lint __int64 #define MAXN 131071 struct HashNode { lint data, id, next; }; HashNode hash[MAXN<

/************************************* ---高次同余方程模板BabyStep-GiantStep--- 输入:对于方程A^x=B(mod C),调用BabyStep(A,B,C),(0<=A,B,C<=10^9) 输出:无解放回-1,有解放回最小非负整数x 复杂度:O(C^0.5),只与C有关,与A,B的大小无关 ************************************/ typedef long long ll; #define HAS

不理解Baby Step Giant Step算法,请戳: http://www.cnblogs.com/chenxiwenruo/p/3554885.html #include <iostream> #include <stdio.h> #include <math.h> #include <string.h> #define SIZE 99991 /* POJ 3243 AC 求解同余方程: A^x=B(mod C) */ using namespace

先给出我所参考的两个链接: http://hi.baidu.com/aekdycoin/item/236937318413c680c2cf29d4 (AC神,数论帝  扩展Baby Step Giant Step解决离散对数问题) http://blog.csdn.net/a601025382s/article/details/11747747 Baby Step Giant Step算法:复杂度O( sqrt(C) ) 我是综合上面两个博客,才差不多懂得了该算法. 先给出AC神的方法: 原创帖

第一篇\(Blog\)... 还是决定把\(luogu\)上的那篇搬过来了. BSGS,又名北上广深 它可以用来求\(a^x \equiv b (mod \ n)\)这个同余方程的一个解,其中\(a,n\)互质. 欧拉定理告诉我们,这里\(a^{\varphi(n)} \equiv 1 (mod \ n)\) 由于\(a^0 \equiv 1 (mod \ n)\),所以这里\(x\)到\(\varphi(n)\)后\(a^x \ mod \ n\)就开始循环了. 所以我们最坏情况就是\(n\)

http://acm.hdu.edu.cn/showproblem.php?pid=2815 题意:裸题... 关于拓展BSGS的详细解释我写了一篇博文:http://www.cnblogs.com/KonjakJuruo/p/5178600.html 题解:又有一个坑,就是N>=P的时候输出无解. #include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #incl

http://poj.org/problem?id=3243 题意:给定X,Z,K,求一个最小的Y满足XY mod Z = K. 关于拓展BSGS的详细解释我写了一篇博文:http://www.cnblogs.com/KonjakJuruo/p/5178600.html 题解:BSGS的拓展版本(因为X和Z不一定互质).这道题挺坑的,如果K>=Z不是输出无解而是让K%=Z. 算是BSGS的模板题,我打了两种版本,就是二分查找和hash.对比两次提交来看,二分省空间,耗时间:Hash省时间,耗空间

摘要写在一瞪眼. #include<iostream> using namespace std; long long exgcd(long long a,long long b,long long &k,long long &t) { if (b==0) { k=1; t=0; return a; } else { long long tp_gcd; tp_gcd=exgcd(b,a%b,k,t); long long temp; temp=k; k=t; t=temp-(a/

链接 BZOJ 2480 虽然是个三倍经验题(2333),但是只有上面这道(BZOJ2480)有 p = 1 的加强数据,推荐大家做这道. 题解 这是一道BSGS(Baby Step Giant Step)的棵题,要考虑的细节还是很多的-- 先讲一下题解吧. 由于每个版本的题设的字母都不尽相同,所以--在下文中我使用的方程是 \[A^x\equiv B\pmod C\] 考虑暴力枚举,可以证明,\(A^x \bmod C\)是周期性的,且周期长度不超过\(C\).那么暴力枚举\([0, C -

先记录一下一些概念和定理 同余:给定整数a,b,c,若用c不停的去除a和b最终所得余数一样,则称a和b对模c同余,记做a≡b (mod c),同余满足自反性,对称性,传递性 定理1: 若a≡b (mod c),对某个整数k有 a+k≡b+k (mod c) a-k≡b-k (mod c)  ak≡bk (mod c)  定理2: 若a≡b (mod c),d≡e (mod c),有 ax+dy≡bx+ey (mod c) ,x,y为任意整数,即同余式可以相加 ad≡be (mod c) ,即同余

一.第四单元作业架构设计 我们第四单元围绕UML图展开,在第四单元开始之前,本来以为我们的工作是学习如何使用UML工具,开始后才意识到我们要做的是解析UML类图.顺序图和状态图.当然,让我们解析的只是冰山一角,但我必须说解析UML图真的是太面向对象了. 1.第一次作业 第一次作业中我们要完成的是实现一个UML类图解析器UmlInteraction,同时有对UML的入门级了解(原来学习UML类图也是这个单元的目的之一),在这次作业中我本来想的是把之前学到的众多面向对象的知识结合起来写一次漂亮的作业

这一章节主要介绍我们在进行数值分析常用的二分.三分和一个近似求解区间积分的辛普森法. 首先介绍二分. 其实二分的思想很好理解并且笔者在之前的一些文章中也有所渗透,对于二次函数甚至单元高次函数的零点求解.线段树还有<algorithm puzzle>当中的“切割钢条”问题,都是基于二分思想. 下面我们通过具体的问题来应用二分这种数值分析的策略. Ex1:按揭贷款 以P%的年利率借贷N元后,在M个月内,以每月还C元的方式还贷.贷款期限内,按照如下形式计算贷款余额. (1)    贷款余额从余额N元

 1.burnside定理,polya计数法 这个专题我单独写了个小结,大家可以简单参考一下:polya 计数法,burnside定理小结 2.置换,置换的运算 置换的概念还是比较好理解的,<组合数学>里面有讲.对于置换的幂运算大家可以参考一下潘震皓的那篇<置换群快速幂运算研究与探讨>,写的很好. *简单题:(应该理解概念就可以了) pku3270 Cow Sorting http://acm.pku.edu.cn/JudgeOnline/problem?id=3270 pku

用于求解高次同余方程A^x≡B(mod C),其中C不一定是素数. http://blog.csdn.net/tsaid/article/details/7354716 这篇题解写得最好. 那啥,这题的坑点请去看discuss. #include<cstdio> #include<cstring> #include<algorithm> #include<cmath> using namespace std; typedef long long ll; vo

Discrete Logging Time Limit: 5000MS   Memory Limit: 65536K Total Submissions: 5577   Accepted: 2494 Description Given a prime P, 2 <= P < 231, an integer B, 2 <= B < P, and an integer N, 1 <= N < P, compute the discrete logarithm of N, b

目录 快速幂 扩展欧几里得 GCD 扩展欧几里得 同余系列 同余方程 同余方程组 一点想法 高次同余方程 BSGS exBSGS 线性筛素数 埃式筛 欧拉筛 欧拉函数 讲解 两道水题 法雷级数 可见点数 原根 欧拉定理 原根部分性质证明(数量证不出来,一个还没填的坑) 扩展:原根的求法 代码 高斯消元 普通 辗转相除法 矩阵树与证明 未了结的坑 无向图 关联矩阵 Kirchhoff矩阵 行列式 求法 代码 证明 柯西-比内公式 小结 @ 快速幂 题目描述 [题意] 求a^b mod c,a,b,

高次同余方程.   BL == N (mod P)求解最小的L. /* A^x=B(mod C) 设x=i*m-j(其中m=ceil(sqrt C)) 并且i∈[1,m],j∈[0,m],以保证x能取到所有的0~C-1之间的数. 为什么只取到0~C-1就行了呢? 根据费马小定理 a^(p-1)=1(mod p)(p是素数),我们可以得到 a^(k mod p-1)=a^k(mod p) 即当k>p-1时,会出现类似于循环节的东西. 那么我们可以得到变形之后的式子 A^(i*m-j)=B(mod