111qqz的小窝

老年咸鱼冲锋!

hdu 1211 RSA (扩展欧几里得算法求逆元 +快速幂)

题目链接

题意:给出p, q, e, l,令n = p * q, fn = (p-1) * (q-1)

给出l个c,计算m = D(c) = cd mod n,其中m为要输入的明文对应的ascii编码,d的计算方法:> calculate d, making d × e mod F(n) = 1 mod F(n), and d will be the private key。

问明文。

 

思路:

出题人JGShining(极光炫影)傻逼。

题意都说不清?

大小写字母一个意思?

脑袋有坑的出题人。

出题人傻逼。

出题人傻逼。

出题人傻逼。

 

 

好了。这道题需要用到扩展欧几里得算法求逆元。。。ksm(a,mod-2)的方法是基于费马小定理,必须mod为质数才可以用。扩展偶记里算法没有这个限制。

用欧几里德算法求模的逆元:

同余方程ax≡b (mod n),如果 gcd(a,n)== 1,则方程只有唯一解。

在这种情况下,如果 b== 1,同余方程就是 ax=1 (mod n ),gcd(a,n)= 1。

这时称求出的 x 为 a 的对模 n 乘法的逆元。

对于同余方程 ax= 1(mod n ), gcd(a,n)= 1 的求解就是求解方程

ax+ ny= 1,x, y 为整数。这个可用扩展欧几里德算法求出,原同余方程的唯一解就是用扩展欧几里德算法得出的 x 。

也就是gcd(a,n,x,y);
然后再(x = x%n + n)%n,得到最小的正整数x,即为a在模n意义下的逆元。

 

 

逆元学习笔记

acdreamer_逆元学习笔记

 

摘重点:

ksm(a,mod-2)的方法求逆元只适用于mod为质数且 gcd(a,mod)==1

扩展欧几里得算法求逆元只适用于gcd(a,mod)==1

扩展欧几里得算法求逆元

acdreamer的博客里提到一种通用的方法,正确性未知(然而有b|a的前提呵呵呵呵呵)

但是你会发现费马小定理和扩展欧几里得算法求逆元是有局限性的,它们都会要求互素。实际上我们还有一

种通用的求逆元方法,适合所有情况。公式如下

 

O(n)求逆元:

其实有些题需要用到的所有逆元,这里为奇质数。那么如果用快速幂求时间复杂度为

如果对于一个1000000级别的素数,这样做的时间复杂度是很高了。实际上有的算法,有一个递推式如下

 

它的推导过程如下,设,那么

对上式两边同时除,进一步得到

再把替换掉,最终得到

初始化,这样就可以通过递推法求出模奇素数的所有逆元了。

另外的所有逆元值对应中所有的数,比如,那么对应的逆元是

 

 

 

codeforces 594 D. REQ (树状数组+欧拉函数+逆元)

题目链接

题意:给出n个数,q个查询,每组一个区间,询问区间中所有数的乘积的欧拉函数%1E9+7的答案是多少。

思路:这道题需要一点欧拉函数的知识。

phi(n)是欧拉函数,意义为小于等于n并且与n互质的数的个数。

To calculate the answer on every query let’s use the formula , where p1, p2, …, pk — all prime numbers which dividedn.

如果知道欧拉函数的这个公式。。。那么这道题就成了水题。。。。

考虑两个数a,b的欧拉函数。

一开始考虑也许有什么性质。。。查了下欧拉函数的wiki
欧拉函数_维基百科
欧拉函数是积性函数(但不是完全积性函数。。因此必须phi(ab) =phi(a)*phi(b)成立当且仅当gcd(a,b)==1)

然而这里并不一定满足互质的条件。。。

 

再想一下。。。发现完全没必要由phi(a)和phi(b)得到phi(a*b)

直接把a*b看成一个数就好了。。。。

后面质因子乘积部分只需要把两部分的并在一起就好了。。。

所以根据上面欧拉函数的公式。。。答案分为两部分。。。

一部分是区间中所有数的乘积。。。

一部分是区间中所有数的不相同的素因子的p-1/p形式的乘积。。。

第一部分预处理前缀积即可。。。由于有%运算。。。所以除的时候需要计算逆元。。。

第二部分的做法同spoj_dquery解题报告

也是离线处理,把询问按照区间右端点排序升序排列,然后lst数组记录上次该数出现的位置。。。用bit维护一个从1到某个数的乘积。。。在撤销的时候同样需要逆元。。。

 

还要注意。。。太长的式子一定要分开写。。。。

因为写错括号顺序调了半天orz…

 

 

 

 

bc #77 div 2 B ||hdu 5651 xiaoxin juju needs help (排列组合,逆元)

题目链接
题意;给出一个字符串,只由小写字母组成,可以任意排列,但是不能减少字符,问最多能得到多少个回文串,答案%1E9+7

思路:排列组合题。 首先考虑无解的情况。统计出每个字母出现的次数,当字符串长度为奇数而且出现次数为奇数的字母的个数多于1个时无解,或者当字符串长度为偶数,出现次数为奇数的字母的个数多于0个时无解。
接下来,由于是回文串,只需要考虑len/2的情况,另一半是一一对应的。
其实就是一共有len/2的元素,其中有一些重复的,然后全排列。 多重元素的排列问题。
答案为(len/2)! % (cnt[1]!)% (cnt[2]!)…即可
哦要先把cnt降序排一下,只考虑cnt[i]>1的元素,然后因为是要考虑一半长度,所以每个cnt[i]/2
那一堆阶乘直接逆元搞就好了。。。。

比赛的时候手滑,把cnt[i]!写成了cnt[i],wa了一发。。。

hdu 5145 NPY and girls

http://acm.hdu.edu.cn/showproblem.php?pid=5145
题意:有n个女孩,编号1..n,第i个女孩在第a[i]个教室,m次访问,每次访问编号[L,R]的女孩,处于同一个教室的女孩一次只能访问一个,问有多少种访问方案。两个不同的方案当且仅当访问的顺序有所不同。

思路:正好刚刚听完学堂在线上的组合数学的那一节,讲到有重复元素的不重复排列的个数的计算方法:可以先将所有元素看成不重复,再除以每个元素的重复度的阶乘(重复度定义为每个元素个数)。

增加一个元素的影响是,乘一个增加的长度,并且除以该元素的重复度(因为每增加一个元素就要除以以此重复度,那么当同一元素c增加到第i次时,除以的就是i的阶乘),减少一个元素的影响正相反。 两种改变都可以O(1)实现,因此可以上莫队。

之前要预处理下逆元。