问题Problem 在codility看到的题目, 题目内容如下 题目内容 英文题目 A non-empty array A consisting of N integers is given. A pair of integers $(P, Q)$, such that $0 ≤ P < Q < N$, is called a slice of array A (notice that the slice contains at least two elements). The average of a slice $(P, Q)$ is the sum of $A[P] + A[P + 1] + … + A[Q]$ divided by the length of the slice. To be precise, the average equals $(A[P] + A[P + 1] + … + A[Q]) / (Q − P + 1)$. ...
问题 设$a$和$b$为正整数, 且$ab+1$整除$a^2+b^2$. 证明$\frac{a^2+b^2}{ab+1}$是完全平方数. 前置知识 完全平方数 如果$a\in N^*$(正整数), 如果$a^2=b$, 那么我们称$b$为完全平方数. 整除 为了智械危机的快速来临, 在这里讲解一下整除:) 如果$\frac{b}{a}=c$, 且$c\in N^*$, 那么我们称a可以整除b. 解题思路 请先尝试一下自己解题, 五分钟没有思路的情况下, 再接着往下看. 证明思路 相信大家还记得高中数学的"韦达定理"(Vieta’s theorem), 其出自于一个处理数论的证明技巧: 韦达跳跃(Vieta jumping), 除了韦达定理外, 还包括了另一个部分, 无穷递增法(method of infinite descent) 韦达定理描述为: 在二元一次方程中, 两个根的和,积与abc(abc为二元一次方程的项)的关系 假设一元二次方程$ax^2+bx+c=0$有两个实数根, 设其为$x_1,x_2$, 则$x_1+x_2=-\frac{b}{a}$, $x_1*x_2=\frac{c}{a}$ 具体推导过程不表. 无穷递增法是一种反证法, 用自然语言表述为 假设方程有解, 并假设X为最小解, 接着再从X出发, 尝试推导出一个更小的解Y. 若能推导成功, 则与刚才假设的"X为最小解"矛盾, 因此证明此方程无解. 回到最开始的问题中, $ab+1$可以整除$a^2+b^2$, 因此$\frac{a^2+b^2}{ab+1}$是一个正整数, 设其为$k$. 接着我们假设有正整数$a,b$满足$\frac{a^2+b^2}{ab+1}=k$, 而$k$不是完全平方数. 最后, 假设在所有满足条件2的正整数中, 有一组是$a_1,b_1$, 他们拥有最小的和, 其中$a_1>b_1$. 因此, 如果我们能证明, 如果有一组数可以比比$a_1,b_1$还要小, 那么我们条件2的假设:$k$不是完全平方数, 就不成立了, 即证明了$k$是完全平方数. 开始解题 $$ \frac{a_1^2 + b_1^2}{a_1 b_1 + 1} = k \tag{1} $$ ...
首先我们看一个非对称加密在现实中的具体应用(笑 有学生没带作业, 老师需要在群里提醒家长, 但直接发学生的照片就会被所有家长知道没带作业的学生是谁, 这样会导致学生和家长都很没面子. 所以老师使用了公钥(大家都能看到的): 学生的鞋子. 大家看到的只是三个学生的鞋子, 并不知道学生具体是谁, 即看到的是密文. 家长看到了鞋子, 因为拥有私钥(即只有家长自己知道自己家孩子穿的什么样的鞋), 所以可以知道老师发的照片中学生是谁, 破解了密文, 这就完成了一次非对称性的加密和解密. 换成严谨一点的语言描述, 如下: A要向B发送信息，A和B都要产生一对用于加密和解密的公钥和私钥。 A的私钥保密，A的公钥告诉B；B的私钥保密，B的公钥告诉A。 A要给B发送信息时，A用B的公钥加密信息，因为A知道B的公钥。 A将这个消息发给B（已经用B的公钥加密消息）。 B收到这个消息后，B用自己的私钥解密A的消息。其他所有收到这个报文的人都无法解密，因为只有B才有B的私钥。 从上文可以看出, 非对称加密体系不要求通信双方事先传递密钥或有任何约定就能完成保密通信，并且密钥管理方便，可实现防止假冒和抵赖，因此，更适合网络通信中的保密通信要求. 原理 根据数论，寻求两个大素数比较简单，而将它们的乘积进行因式分解却极其困难，因此可以将乘积公开作为加密密钥. 获取公钥私钥过程 选择两个很大的素数p和q 这里取$p=67,q=71$ 计算$n=p⋅q, n$公开, 即为公钥的一部分. (如果$n=p⋅q=4757_{(10)}=1001010010101_{(2)}$, 二进制的n为13位, 则称该加密为13位加密, 实际应用中一般才用1024位或2048位的加密来保证安全). 计算 n 的欧拉函数 $φ(n)$ 设$m=φ(n)=φ(q)⋅φ(q)=(q−1)(p−1)=66×70=4620.$ 在数论，对正整数n，欧拉函数φ(n)是小于或等于n的正整数中与n互质的数的数目（因此φ(1)=1(1), φ(8)=4(1,3,5,7）, 这里的p,q都是质数, 所以从1到(n-1)都与其互质, φ(n)=n−1 再选一个数字e, e与m互质, 且1<e<m, e也是公开的, 即公钥的另一部分. 这里取e=101, 这里e的选择有一个小坑, 我们一会再说 找到一个整数 d，可以使得 e∗d 等价于$e*d−1=y∗m, y∈N+$, 将数字带入$101×d−1=y×4757$, 这里可用扩展欧几里得算法解, 下文给出过程, 这里省略. 给出结果$(d,y)=(1601,35)$, 即$d=1601$, 从这里可以看出, d是由我们上面第4步任意取的e决定的, 所以我们只要选取不同的e, 就可以得到不同的d, 就是不同的密钥对. ...
问题描述 已知有一个长度为 26 的整型数组, 分别代表 26 个字母的个数, 问这些字母能组成多少种不同的字符串(取模 1000000007). 问题求解 纯暴力 开始觉得很简单, 纯迭代问题, 抬手就来. int calc(int[] nums) { int ret = 0; for (int i = 0; i < nums.length; i++) { if (nums[i] > 0) { nums[i]--; ret += calc(nums); ret %= 1000000007; nums[i]++; } } return ret > 0 ? ret : 1; } 结果超时, 不行, 看来只能用数学方法求解. 数学方法 $$ Sum=\dfrac{A_{字母总数}^{字母总数}}{A_{A的数量}^{A的数量}\times……\times A_{2}^{2}} $$ 题目没有讲太清楚(是否这些字母一定要全部使用), 这里为了简单就假设全部使用. 解法一：排列组合. 生成字符串长度是 $sum=a_0+a_1+a_2+…+a_{25}$. 放 $a$ , 有$(sum, a0)$种选择的方法; 放$ b$, 有$(sum - a0, a1)$种方法; 放 $c$, 有$(sum - a0 - a1, a2)$种方法…..直到最后 程序 private long solve1(int[] letters) { int sum = 0; for (int c : letters) { sum += c; } BigInteger r = BigInteger.ONE; for (int c : letters) { BigInteger s = choose(sum, c); r = r.multiply(s); sum -= c; } return r.longValue(); } private static BigInteger choose(int n, int k) { BigInteger r = BigInteger.ONE; for (int i=0; i<k; i++) { r = r.multiply(BigInteger.valueOf(n - i)); } for (int i=2; i<=k; i++) { r = r.divide(BigInteger.valueOf(i)); } return r; } 解法 2: EGF (指数生成函数)。 这是个排列问题所以用指数生成函数. ...