题目链接

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

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

acdreamer_逆元学习笔记

摘重点：

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

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

扩展欧几里得算法求逆元

acdreamer的博客里提到一种通用的方法，正确性未知。（然而有b|a的前提呵呵呵呵呵）

题目链接

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

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

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

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

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

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