我要分享技术
0%

ARTS-10

发表于 更新于 分类于

ARTS-10

Algorithm

引言

做了太多的二叉, 本来想着尽量做一些从数学上的高效求解的题目, 但是我的博客数学公式渲染有问题,我还没能搞定, 所以这次来个DP问题。

Description

70. Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

Note: Given n will be a positive integer.

Example 1:

Input: 2
Output: 2

Explanation: There are two ways to climb to the top. 1. 1 step + 1 step 2. 2 steps

Example 2:

Input: 3
Output: 3

Explanation: There are three ways to climb to the top. 1. 1 step + 1 step + 1 step 2. 1 step + 2 steps 3. 2 steps + 1 step

大意

有一个n层的楼梯, 每次你可以迈一层或者两层, 问, 爬到楼梯顶部一共有多少种走法。

思路

典型的动规问题。虽然也有其他一些不同的解法, 例如穷举, 但是效率太低,并不合适。

这里具体不再展开, 本篇解法会在Share当中分享。

Code

代码可以更加精简, 基本4~5行就能够完成, 但是我为了尽量通过代码能体现思路, 按照思路的进行续来编码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int climbStairs(int n) {
        if (n==1)
          return 1;
        if (n==2)
          return 2;
      
        int stair_1 = 2;    // pre stair ways
        int stair_2 = 1;    // the second pre stair ways
        int stair = 3;
        while (stair++ <= n) {
          int old = stair_2;
          stair_2 = stair_1;
          stair_1 = stair_2 + old;
        }
        return stair_1;
    }
};

Result

Success Details

Runtime: 4 ms, faster than 87.64% of C++ online submissions for Climbing Stairs.

Memory Usage: 8.2 MB, less than 78.25% of C++ online submissions for Climbing Stairs.

Time Submitted Status Runtime Memory Language
a few seconds ago Accepted 4 ms 8.2 MB cpp

Review

Tips

RSA 非对称加密算法原理

欧拉函数

在数论中，对正整数n，欧拉函数 \(\varphi(n)\) 是小于或等于n的正整数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为φ函数（由高斯所命名）或是欧拉总计函数（totient function，由西尔维斯特所命名）。 欧拉函数

RSA 算法的核心: 欧拉定理

. > 在数论中，欧拉定理（也称费马-欧拉定理或欧拉 \(\varphi\) 函数定理）是一个关于同余的性质。欧拉定理表明，若 n,a为正整数，且 n,a 互素（即 \(\gcd(a,n)=1\) ），则

\[\begin{equation}a^{\phi{\left(n\right)}} \equiv 1 \pmod n \end{equation}\]

欧拉定理

费马小定理: 欧拉定理的特例

费马定理的表达式 :

\[ a^{\phi{\left(n\right)}} \equiv 1 \pmod n \]

在特殊情况下, 当n为质数时, \(\varphi(n)=n-1\), 此时, 欧拉定理的表述即为:

\[ a^{n-1} \equiv 1\pmod n \]

这个公式就是费马小定理。

模反元素

如果两个正整数 a 和 n 互质, 那么一定存在一个整数 b 满足:

\[ ab \equiv 1\pmod n \]

即, (ab - 1)能被n整除。 b就叫做a的模反元素。 显然的, 模反元素并不唯一, 对于模反元素b, 对于所有的正整数 $m=b+kn$也为a的模反元素。

模反元素必然存在

对费马定理进行变形:

\[ a^{\phi\left({n}\right)}\equiv a\times a^{\phi\left(n\right)-1}\equiv 1 \pmod n \]

在此变形中, \(a^{\phi\left(n\right)-1}\) 即为a的模反元素。

RSA 基本概念

我们约定:

  • RSA加密秘钥为E, 它是一个大整数。
  • RSA解密秘钥为D, 它是一个大整数。
  • RSA加密和解密需要用的模数N, 它是一个大整数。
RSA 加密过程

\[ 密文 = 明文^E mod N \]

RSA 加密过程就是这么简单, 它对明文做一个E次幂运算, 然后对N取模。 在这个过程中, E和N的组合就是公钥。

RSA 解密过程

对应的, RSA的解密过程也非常简单:

\[ 明文 = 密文^D mod N \]

RSA 的加密和解密过程完全一致, 只是它们换了一个秘钥, 进行了完全一样的运算。 在这个过程中, D和N的组合就是私钥。

非对称秘钥对的生成

在基本概念中, 约定了几个量, E, D, N 在这里,我么继续沿用, 额外的,在生成密钥对的过程中, 引入一个新的量L, 它只用于生成密钥对, 但是最终结果中我们并不体现它。

1. 求N

准备两个大质数p, q。(p和q要最够大)

\(N=p \times q\)

2. 求L

L是 p-1 和 q-1 的最小公倍数。

\(L=lcm(p-1. q-1)\)

实际上, 理论公式上, L应为ϕ(n), 这样后面的一系列推倒便是欧拉定理的应用了, 但是在实际中,它可以化简为更小的最小公倍数L, 这里,我们使用了实际中的化简方案

3. 求E

E是一个比1大, 比L小的数字,且E和L要互质, 即 E和L的最大公约数为1, 表达为数学语言为。

\[1 < E < L\\ \gcd(E, L) = 1\]

计算E的过程我们采用随机穷举的模式, 使用伪随机数生成器, 随机生成一个1和L之间的数字, 判断是否满足它与L互质, 如果不满足, 则重复生成并判断下一个随机数。

至此, RSA的公钥部分E,N我们已经得到了, 公钥: (E, N)。

我们加入E和L互质的这个条件,是为了满足我们需要的解密参数D一定存在

4. 求D

\(1 < D < L\)

\(E \times D\ mod\ L = 1\)

按照上述的限制条件, 计算出D, 至此, 私钥部分也计算完成, 私钥为(D, N)。

Share

算法-动态规划 Dynamic Programming--从菜鸟到老鸟

End