Loading [MathJax]/jax/output/HTML-CSS/jax.js

任意模数的K次剩余 /HDU 3930 Broot/BZOJ 2219 数论之神/51nod 1123 X^A mod B

前言

难以置信, 遇到这个问题竟然是因为做一道CTF Reverse的题, 实际上我以前打ACM的时候都没有写过任意模数的K次剩余这种东西. 最简单的模质数的K次剩余的例题是
“`HDU 3930 Broot“`, 进阶版本(模任意奇数的K次剩余)的例题是“`BZOJ 2219 数论之神“`, 而终极版本(任意模数的K次剩余)似乎可以交的题只有“`51nod 1123“`, 截至本文写作时只有44个AC. 然而这个CTF题本身就有50多个通过了. ~~CTF>ACM 实锤~~ (暴论)

其实是因为这个Reverse的题里面幂指数是质数,所以会跟模数互质,然后就可以用RSA的方法来做了. 其次该题目更多的工作在于去花指令混淆上, 而非算法破解.

OK那么就来看一下这个问题从最简单的版本到终极版本怎么求解吧…

模质数的K次剩余

已知a, b, p, 求使得

xab(mod p)

成立的所有 x. 其中 p 是质数.

由于 p 是质数, 所以 p 存在原根 g , 此时对于模 p 意义下的任意数 w (0wp1) 存在唯一的 i (0ip1) 使得 wgi(mod p).

由此可以将最终的答案用 g 来表示: x=gc, 带入上式转化为求解

(gc)a(ga)cb(mod p)

此时 g, a, b, p, 已知, 只需要解出来 c. 此时相当于求解离散对数, 使用 Baby-Step-Giant-Step 可以在 O(p) 时间内得到一个特解 x0gc(mod p).

在已知一个特解的情况下求出所有解是简单的, 由原根的性质可知 gφ(p)1(mod p), 因此:

tZ,xagca+tφ(p)b(mod p)

因此所有的解为:

tZ,atφ(p),xgc+tφ(p)a(modp)

上面幂次部分要能整除必须要有agcd(a,φ(p))t, 可以设 t=agcd(a,φ(p))i, 于是得到所有的解为:

iZ,xgc+φ(p)gcd(a,φ(p))i(modp)

HDU 3930 Broot 代码:

继续阅读“任意模数的K次剩余 /HDU 3930 Broot/BZOJ 2219 数论之神/51nod 1123 X^A mod B”

[数论][图论][思维] codeforces 1325 E Ehab’s REAL Number Theory Problem

codeforces 1325 E

题意:给定一个长度1e5的数组a1ai106 ,满足 ai的因子数量不超过7. 求 a 的最短的满足所有元素相乘结果为完全平方数的子序列的长度。

这个题目做的时候。。一直在想怎么dp。。。完全没往图的方向想。太久没做题了就是这样,丢掉了很多东西,sigh
继续阅读“[数论][图论][思维] codeforces 1325 E Ehab’s REAL Number Theory Problem”

[类欧几里得][位运算] 2019牛客暑期多校训练营(第九场)I KM and M

题目链接

题意:

Nk=1((kM)&M)mod(109+7)

其中 1N1018 , 1M1011

题解:

按位来做,考虑每一个二进制位i, 假设pi是 M 中从小到大第i位上的0/1), 然后我们又可以用取模和取整来取代某一位上的运算,比如当前处理的是第i位 ,就可以写成 Nk=1(kM2i)2Nk=1(kM2i+1)
这显然是一个类欧几里得的模板式子,我们只需要套用一下模板即可。最后把所有位的答案累加起来即可。
继续阅读“[类欧几里得][位运算] 2019牛客暑期多校训练营(第九场)I KM and M”

[离线处理][scheduling][数论结论][x] HDU5869 Different GCD Subarray Query

题目链接

题意:

给定 N 个数字, Q 次询问,每次询问为查询下标在 [l,r] 之间的所有数字中所有可能的子段的 gcd 有多少种。N,Q<105,ai<106

题解:

首先一个重要的结论:以固定点为结尾的子段的 gcd 种数不超过 max(n,log(max(ai))) 证明:每次往原有的序列里加入一个数字的话, gcd 要么不变,要么至少变为原来的1/2,因此为指数级减小。

有了这个结论,我们可以试着来枚举一个端点考虑本题,不妨枚举每个段的右端点rj , 假设集合S表示以rj1 为结尾的所有 gcd ,那么要求出以rj为结尾的所有 gcd ,只需遍历S中的每个数字dk,计算其与ajgcd ,放入新集合S即可。这样的话我们可以得到一个空间为O(nlogn)的结果,表示以每个点为结尾的所有段的 gcd 都是哪些数字。

现在来考虑查询。每次查询的话是要求出来[l,r]之间所有可能的 gcd 。直接暴力不可取,由上面的结果可以试着考虑能否转化为前缀问题。可以发现,如果我们对所有的[l,r]离线处理,按r从小到大排序,并且按照这个顺序来调整已经遇到过的 gcd 的信息的话,每次的查询只需要考虑有多少个 gcd 出现的最右左端点大于等于l,这句话具体的意思是,一个 gcd 可能出现过了很多次,不同的段都可以得到这个 gcd ,但是我们只考虑这些段中左端点l_j最大的那个点pj,这样的话如果l<=pj那么可以确定[l,r]中一定有这个 gcd (种类+1),这就就转化成了一个计数问题。 继续阅读“[离线处理][scheduling][数论结论][x] HDU5869 Different GCD Subarray Query”

[组合数学][数论][矩阵][优化][Polya][状压DP][x] XDOJ 1296 敬老师的手环II

去年校赛的时候感觉此题难的一批,,,昨天做polya练习题的时候做到了poj 2888去翻了下matrix67大神的十个利用矩阵乘法解决的经典题目中的第9题才恍然大悟。。。Oooooor2 做完这俩题再来看XDOJ的这个题已经是自然而然就可以搞出结果的了。

这个题的思想就是:把每一列3*1的小方格当成一个“珠子”,把他可能的8种情况当成“颜色”,然后这些颜色同时也代表状态,类似于poj2888的颜色相邻限制,这里的状态之间“能不能相邻”其实就是在状压dp里“能不能转移”的限制,不同状态之间的转移图如下(来自matrix67的那篇文章

继续阅读“[组合数学][数论][矩阵][优化][Polya][状压DP][x] XDOJ 1296 敬老师的手环II”

[数论][二次剩余应用][组合数][等比数列] ZOJ 3774 Power of Fibonacci

主要是利用了斐波那契数列对mod1e9+9时二次剩余的性质。说起来这个性质也是很奇葩,只见过两次应用这个题目的情况,一个是这个题一个是/cf.
二次剩余的定义是 当存在某个x使得x^2 \equiv d(mod p)成立时,称“d是模p的二次剩余”,当对任意不成立时,称“ d是模 p的二次非剩余”
而对于斐波那契数列有更具体的性质:
继续阅读“[数论][二次剩余应用][组合数][等比数列] ZOJ 3774 Power of Fibonacci”

[二维DP][组合计数][利用对称性简化问题] UVALive 3295

https://vjudge.net/problem/UVALive-3295

这个题目和3720很像,尤其是在应用对称性的时候。这种题目有个很有趣的地方就是他每次都是对局部进行刻画然后得到了全局的信息,或者可以这么说,按照某一种策略使得某种属性所有的状态都被考虑进去。在这里就是计算一个共线的点的问题,按照和题目3720算法本身的推其实是只能算出来“斜率为正”的一类斜线,但是算的是“所有的斜率为正”的斜线,也就是覆盖了每一种情况,那么剩下的情况其实只有水平竖直和斜率为负的斜线,但是由对称性可知斜率为负的斜线一定和斜率为正的斜线数量相等,因此只需要*2即可,而我自己一开始一直在纠结的问题就是怎么算出来这些反向斜线,其实最后全局考虑只需要把算出来的正向斜线情况*2即可。最后的结果就是C(3,(m+1)*(n+1))-共线的三点数量。
wa的话有一个问题是,在gcd的算法中如果a和b有一个数字为0那么返回值就会是0,这种情况在这里的递推过程中是会出现问题的,需要注意让循环从2开始,也算是一个小小的坑吧。。以前没有注意到。

继续阅读“[二维DP][组合计数][利用对称性简化问题] UVALive 3295”

[组合数学][数论][思维][空间对称转化][充要条件] UVALive 3720 Highways

很有意思的一个组合数学题。

整个题的最核心的思想就是,两个线段共线的判断!只要有两个点就可以确定一条线段(直线),那么只要再多一个点就可以确定这个点是否在和当前的这条线段共线了!所以两种算法的思想都在于一个2

第一种方法:最纠结的问题还是在于,怎么去重。想到了枚举角度的方法却没有想到怎么去重,还是思维不行。第一种方法是每次枚举所有可能的矩形,然后计算对角线的数量,这个很好算也就是有多少个矩形,直接(n-i+1)*(m-j+1)就行了。但是我们考虑的时候首先只考虑gcd(i,j)==1的情况,这种情况一定说明这种对角线的角度第一次出现(因为我们从小到大枚举i和j),所以对答案贡献为正,还有一种情况是gcd(i,j)==2,这说明之前已经出现过了这种对角线,所以这里要减去对应的数量,注意这里是最重要的:减去的是对应的数量,然后其他的gcd值不用+也不用-。原因就在于,如果你有一个4*4的或者3*3的矩形对角线重算了,那么在清除gcd为2的那一步当中其实就已经清除了所有的重复对角线!因为这个2会按照不同的起始点一直推下去。 继续阅读“[组合数学][数论][思维][空间对称转化][充要条件] UVALive 3720 Highways”

[数论][暴力][分段] UVA 11754 Code Feat

之所以写这个题是因为他提供了一种新的解决问题的思路。。两个暴力算法结合起来竟然就不暴力了。。

首先直接暴力枚举每个set里的余数然后解同余方程组可以得到一个Πki复杂度的算法,但是这个在k太大的时候会爆,然后k很大的时候就用了同余方程的另一种暴力解法,找到一个同余方程枚举他的所有解然后去判断其他的等式是否满足。。。这个在k比较大的时候比较快(但是感觉这俩算法组合还是有点看RP
代码基本上都是抄的书上就这。不过调了下LIMIT的范围发现从100到500000都可以过。。

继续阅读“[数论][暴力][分段] UVA 11754 Code Feat”

正在加载中...