题目链接

题意：给出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的前提呵呵呵呵呵）

题目链接

题意：

Given a n × n matrix A and a positive integer k, find the sum S = A + _A_2 + _A_3 + … + Ak.

思路： 对k进行二分。

比如，当k=6时，有： A + A^2 + A^3 + A^4 + A^5 + A^6 =(A + A^2 + A^3) + A^3*(A + A^2 + A^3) 应用这个式子后，规模k减小了一半。我们二分求出A^3后再递归地计算A + A^2 + A^3，即可得到原问题的答案。

梦。。。。 设定大概是我身上有某种可以产生军用价值的变异... 所以要杀掉我做研究。。。？ 但是我不同意2333 于是把我抓了起来。。。判了10年有期徒刑的样子。。。 罪名好想是不支持社会主义建设。。。。？？？ 我还记得很清楚。。。。有人和我讲什么“好好改造，早日回归社会” 鬼啊。当时第一个念头是，我今年的比赛还没打。。。。10年出来以后就不能参加比赛了orz。。。

(\alpha+\beta\geq\frac12)

20180101_test:

(\alpha+\beta\geq\frac12)

$$\left[ \begin{matrix}a&b\c&\alpha\end{matrix} \right]$$

\left( \begin{matrix}a&b\c&\alpha\end{matrix} \right)

题目链接

题意：求f[n] % 10000,f为斐波那契数。

思路：按照题目给出的公式，或者按照加速线性递推式的方法都可以。。。

因为把模数的1E4手滑写成1E4+7结果调了半天也是没谁了呵呵呵呵。

找到了篇四年前空间中的旧文，也是有点感动2333.

快速求解多项递推式

问题描述:

已知 F(n) = AF(n-1) + BF(n-2) + CF(n-3)+.....

求解 F(n)%P

分析:

＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊＊

参考资料：

十个利用矩阵乘法解决的经典题目

题目链接

题意：求在小于等于N的正整数中有多少个X满足：X mod a[0] = b[0], X mod a[1] = b[1], X mod a[2] = b[2], …, X mod a[i] = b[i], … (0 < a[i] <= 10)。

思路：先用扩展欧几里得算法（excrt）解一般同余方程求出一个特解R,然后通解R' = R + k * LCM(a1..am)

题目链接

题意：给出k个方程，形式为 x==r1,求最小的正数x，无解输出-1.

思路：首先很容易让人联想到crt.

然而crt的使用条件是，所有的m(也就是这道题中的a)两两互质，这道题并不满足，因此不能使用crt.