扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
下载作业帮安装包
扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
求直线(x+y-z-1=0 x-y+z+1=0)在平面x+y+z=0上的投影直线方程
作业帮用户
扫二维码下载作业帮
拍照搜题，秒出答案，一键查看所有搜题记录
在直线上取两点（0,0,-1）和（0,1,0）,可得直线的方向向量 v1=（0,1,1）,而平面 x+y+z=0 的法向量为 n1=（1,1,1）,所以,由 v1、n1 确定的平面的法向量为 n2=v1×n1=（0,1,-1）,那么,所求直线的方向向量为 n1×n2=（-2,1,1）,由于已知直线与已知平面交于点（0,1/2,-1/2）,所以,所求直线方程为 (x-0)/(-2)=(y-1/2)/1=(z+1/2)/1 ,化简得 x=1-2y= -1-2z .
为您推荐：
其他类似问题
看到这题的思路：1、直线的平面束为
x+y-z-1+λ（x-y+z+1）=0 即 （λ+1）x+（1-λ）y+（λ-1）z+（λ-1）=02、平面x+y+z=0的法向量
n1={1,1,1}3、由平面束中的某一平面Π与平面x+y+z=0垂直得：
（λ+1）·1+
（1-λ）·1+ （λ-1）·1=0 得 λ=-14、代入平...
扫描下载二维码这样一道vb提：x＝5，y＝15，z＝3，计算（y mod10）×10＋y\10_百度知道
这样一道vb提：x＝5，y＝15，z＝3，计算（y mod10）×10＋y\10
我刚学vb，急死我了，什么都不会，求高手帮一把，把代码写一下就可以了，我还想问一下立即窗口有什么用。
我有更好的答案
源代码粘贴进去就可以用 创建一个text文本框和一个command按钮Private Sub Command1_Click()x = 5: y = 15: z = 3Text1 = &(y Mod 10) * 10 + y \ 10=& & (y Mod 10) * 10 + y \ 10End Sub
采纳率：20%
创建一个命令按钮，在命令按钮的点击事件中写以下代码 Private Command1 _Click() dim intx as integerdim inty as integerdim intz as integerdim intA as integer
intA= (y mod 10) *10 + y\10
print intAend sub
Private Sub Form_Load()AutoRedraw = TrueDim x As IntegerDim y As IntegerDim z As IntegerDim a As Integerx = 5y = 15z = 3a = (y Mod 10) * 10 + y \ 10Print aEnd Sub立即窗口 *MSDN解释：在中断模式时会自动打开，且其内容是空的。1.键入或粘贴一行代码，然后按下 ENTER 键来执行该代码。2.从立即窗口中复制并粘贴一行代码到代码窗口中，但是立即窗口中的代码是不能存储的。 立即窗口可以拖放到屏幕中的任何地方，除非已经在“选项”对话框中的“可连接的”选项卡内，将它设定为停放窗口。可以按下关闭框来关闭一个窗口。如果关闭框不是可见的，可以先双击窗口标题行，让窗口变成可见的。注意
在中断模式下，立即窗口中的语句，是根据显示在过程框的内容或范围来执行的。举例来说，如果键入 Print variablename，则输出的就是局域变量的值。这和在程序中止时 Print 方法在正在执行的过程产生一样
为您推荐：
其他类似问题
换一换
回答问题，赢新手礼包
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。X+Y+Z=35 X/16+Y/10+Z/20=2.5 Z/16+Y/10+X/20=2.65怎么求x y z_百度知道
X+Y+Z=35 X/16+Y/10+Z/20=2.5 Z/16+Y/10+X/20=2.65怎么求x y z
我有更好的答案
你好！根据给的条件可以得出：X/16+Y/10+Z/20=2.5
可化为 5X+8Y+4Z=2.5*80 （1式）Z/16+Y/10+X/20=2.65
可化为 5Z+8Y+4X=2.65*80
（2式）（1式）-（2式） 得 X=8+ZY=35-X-Z=27-2Z
带入 （1式）
X=16 Y=11 Z=8
采纳率：31%
根据已知条件：X/16+Y/10+Z/20=2.5
可化为 5X+8Y+4Z=2.5*80 （1式）Z/16+Y/10+X/20=2.65
可化为 5Z+8Y+4X=2.65*80
（2式）（1式）-（2式） 得 X=8+ZY=35-X-Z=27-2Z
带入 （1式）
X=16 Y=11 Z=8
由已知X/16+Y/10+Z/20=2.5
可化为 5X+8Y+4Z=2.5*80 （1式）Z/16+Y/10+X/20=2.65
可化为 5Z+8Y+4X=2.65*80
（2式）（1式）-（2式） 得 X=8+ZY=35-X-Z=27-2Z
带入 （1式）
X=16 Y=11 Z=8
为您推荐：
其他类似问题
换一换
回答问题，赢新手礼包
个人、企业类
违法有害信息,请在下方选择后提交
色情、暴力
我们会通过消息、邮箱等方式尽快将举报结果通知您。& &&int&gcd(int&a,&int&b)&{& & & &&return&b&?&gcd(b,&a%b)&:&a;& & }& & & 这个函数揭示了一个约定俗成的概念，即任何非零整数和零的最大公约数为它本身。& & &【例题8】f[0] = 0, 当n&1时，f[n] = (f[n-1]+a) % b，给定a和b，问是否存在一个自然数k (0 &= k& b)，是f[n]永远都取不到的。& & & 永远有多远？并不是本题的范畴。& & & 但是可以发现的是这里的f[...]一定是有循环节的，如果在某个循环节内都无法找到那个自然数k，那么必定是永远都找不到了。& & & 求出f[n]的通项公式，为f[n] = an % b，令an = kb + r，那么这里的r = f[n]，如果t = gcd(a, b)，r = an-kb = t ( (a/t)n - (b/t)k )，则有t|r，要满足所有的r使得t|r,只有当t = 1的时候，于是这个问题的解也就出来了，只要求a和b的gcd，如果gcd(a, b) & 1，则存在一个k使得f[n]永远都取不到，直观的理解是当gcd(a, b) & 1，那么f[n]不可能是素数。& & & 2、扩展欧几里德定理& & & a、线性同余& & & 线性同余方程（也可以叫模线性方程）是最基本的同余方程，即ax≡b (mod n)，其中a、b、n都为常量，x是未知数，这个方程可以进行一定的转化，得到：ax = kn + b,这里的k为任意整数，于是我们可以得到更加一般的形式即：ax + by + c = 0，这个方程就是二维空间中的直线方程，但是x和y的取值为整数，所以这个方程的解是一些排列成直线的点集。& & & b、同余方程求解& & & 求解同余方程第一步是转化成一般式：ax + by = c，这个方程的求解步骤如下：& & & i) 首先求出a和b的最大公约数d = gcd(a, b)，那么原方程可以转化成d(ax/d + by/d) = c，容易知道(ax/d + by/d)为整数，如若d不能整除b，方程必然无解，算法结束；否则进入ii)。& & & ii) 由i)可以得知，方程有解则一定可以表示成 ax + by = c = gcd(a, b)*c'，那么我们先来看如何求解d = gcd(a, b) = ax + by，根据欧几里德定理，有：& & & d = gcd(a, b) = gcd(b, a%b) = bx' + (a%b)y' = bx' + [a-b*(a/b)]y' = ay' + b[x' - (a/b)y']& & & 于是有x = y', &y = x' - (a/b)y'。& & & 由于gcd(a, b)是一个递归的计算，所以在求解(x, y)时，(x', y')其实已经利用递归计算出来了，递归出口为b == 0的时候（对比辗转相除，也是b == 0的时候递归结束），那么这时方程的解x0 = 1, y0 = 0。代码如下：& &&#define&LL&__int64&&&&LL&Extend_Euclid(LL&a,&LL&b,&LL&&X,&LL&&Y)&{& & & & LL&q,&& & & & & & & & & &if(&!b&)&{& & & & & & X&=&1;&Y&=&0;& & & & & & & & & & & & & &&return&a;& & & & }else&{&&&&&&&&&&&&q&=&Extend_Euclid(b,&a&%&b,&X,&Y);&&&&&&&&&&&&temp&=&X;&&&&&&&&&&&&X&=&Y;&&&&&&&&&&&&Y&=&temp&-&(a&/&b)&*&Y;& & & & & & & & & & & & & & &return&q;& & & & }&&&&}& & & 扩展欧几里德算法和欧几里德算法的返回值一致，都是gcd(a, b)，传参多了两个未知数X, Y，采用引用的形式进行传递，对应上文提到的x, y，递归出口为b == 0，这时返回值为当前的a，因为gcd(a, 0) = a，(X, Y)初值为(1, 0)，然后经过回溯不断计算新的(X, Y)，这个计算是利用了之前的(X, Y)进行迭代计算的，直到回溯到最上层算法终止。最后得到的(X, Y)就是方程gcd(a, b) = ax + by的解。& & & 通过扩展欧几里德求的是ax + by = gcd(a, b)的解，令解为(x0, y0)，代入原方程，得：ax0 + by0 = gcd(a, b)，如果要求ax + by = c = gcd(a, b)*c'，可以将上式代入，得：ax + by = c = (ax0 + by0)c'，则x = x0c', y = y0c'，这里的(x, y)只是这个方程的其中一组解，x的通解为 { x0c' + kb/gcd(a, b) | k为任意整数 }，y的通解可以通过x通解的代入得出。& & 【例题9】有两只青蛙，青蛙A和青蛙B，它们在一个首尾相接的数轴上。设青蛙A的出发点坐标是x，青蛙B的出发点坐标是y。青蛙A一次能跳m米，青蛙B一次能跳n米，两只青蛙跳一次所花费的时间相同。数轴总长L米。要求它们至少跳了几次以后才会碰面。&& & & 假设跳了t次后相遇，则可以列出方程：(x + mt) % L = (y + nt) % L& & & 将未知数t移到等式左边，常数移到等式右边，得到模线性方程：(m-n)t%L = (y-x)%L & （即 ax≡b (mod n) 的形式）& & & 利用扩展欧几里德定理可以求得t的通解{ t0 + kd | k为任意整数 }，由于这里需要求t的最小正整数，而t0不一定是最小的正整数，甚至有可能是负数，我们发现t的通解是关于d同余的，所以最后的解可以做如下处理：ans = (t0 % d + d) % d。& & & c、逆元& & & 模逆元的最通俗含义可以效仿乘法，a*x = 1，则称x为a在乘法域上的逆（倒数）；同样，如果ax≡1 (mod n)，则称b为a模n的逆，简称逆元。求a模n的逆元，就是模线性方程ax≡b (mod n)中b等于1的特殊形式，可以用扩展欧几里德求解。并且在gcd(a, n) & 1时逆不存在。& & & 3、中国剩余定理& & & 上文提到了模线性方程的求解，再来介绍一种模线性方程组的求解，模线性方程组如图二-3-1所示，其中(ai, mi)都是已知量，求最小的x满足以下n个等式：图二-3-1& & & 将模数保存在mod数组中，余数保存在rem数组中，则上面的问题可以表示成以下几个式子，我们的目的是要求出一个最小的正整数K满足所有等式：& & & K = mod[0] * x[0] + rem[0] & & (0)& & & K = mod[1] * x[1] + rem[1] & & (1)& & & K = mod[2] * x[2] + rem[2] & & (2)& & & K = mod[3] * x[3] + rem[3] & & (3)& & & ... ...& & &这里给出我的算法，大体的思想就是每次合并两个方程，经过n-1次合并后剩下一个方程，方程的自变量取0时得到最小正整数解。算法描述如下：& & & i) & 迭代器i = 0& & & ii) &x[i] = (newMod[i]*k + newRem[i]) & & & & & &(k为任意整数)& & & iii) 合并(i)和(i+1)，得 mod[i] * x[i] - mod[i+1] * x[i+1] = rem[i+1] - rem[i]& & & & & &将x[i]代入上式，有 newMod[i]*mod[i]*k - mod[i+1] * x[i+1] = rem[i+1] - rem[i] - newRem[i]*mod[i]& & & iv) &那么产生了一个形如 a*k + b*x[i+1] = c的同余方程，& & & & & &其中a = newMod[i]*mod[i], b = - mod[i+1], c = rem[i+1] - rem[i] - newRem[i]*mod[i]& & & & & & & & & & & &求解同余方程，如果a和b的gcd不能整除c，则整个同余方程组无解，算法结束；& & & & & & & & & & & &否则，利用扩展欧几里德求解x[i+1]的通解，通解可以表示成 x[i+1] = (newMod[i+1]*k + newRem[i+1]) & & & & & &(k为任意整数)& & & v) &迭代器i++,如果i == n算法结束，最后答案为 newRem[n-1] * mod[n-1] + rem[n-1]；否则跳转到ii)继续迭代计算。& & & 4、欧拉函数& & & a、互素& & & 两个数a和b互素的定义为：gcd(a, b) = 1，那么如何求不大于n且与n互素的数的个数呢？& & & 朴素算法，枚举i从1到n，当gcd(i, n)=1时计数器++，算法时间复杂度O(n)。& & & 这里引入一个新的概念：用φ(n)表示不大于n且与n互素的数的个数，该函数以欧拉的名字命名，称为欧拉函数。& & & 如果n是一个素数，即n = p，那么φ(n) = p-1（所有小于n的都互素）；& & & 如果n是素数的k次幂，即n = p^k，那么φ(n) = p^k - p^(k-1) （除了p的倍数其它都互素）；& & & 如果m和n互素，那么φ(mn) = φ(m)φ(n)（可以利用上面两个性质进行推导）。& & & 将n分解成如图二-4-1的素因子形式，那么利用上面的定理可得φ(n)如图二-4-2所示：图二-4-1图二-4-2& & & 前面已经讲到n的因子分解复杂度为O(k)，所以欧拉函数的求解就是O(k)。& & & b、筛选法求解欧拉函数& & & &由于欧拉函数的表示法和整数的素数拆分表示法很类似，都可以表示成一些素数的函数的乘积，所以同样可以利用筛选法进行求解。伪代码如下：& &&#define&MAXP&2000010&&&&#define&LL&__int64&&&&void&Eratosthenes_Phi()&{&&&&&&&&notprime[1]&=&true;&&&&&&&&for(int&i&=&1;&i&&&MAXP;&i++)&phi[i]&=&1;&&&&&&&&for(int&i&=&2;&i&&&MAXP;&i++)&{&&&&&&&&&&&&if(&!notprime[i]&)&{&&&&&&&&&&&&&&&&phi[i]&*=&i&-&1;&&&&&&&&&&&&&&&&//&和传统素数筛法的区别在于这个i+i&&&&&&&&&&&&&&&&for(int&j&=&i+i;&j&&&MAXP;&j&+=&i)&{&&&&&&&&&&&&&&&&&&&&notprime[j]&=&true;&&&&&&&&&&&&&&&&&&&&int&n&=&j&/&i;&&&&&&&&&&&&&&&&&&&&phi[j]&*=&(i&-&1);&&&&&&&&&&&&&&&&&&&&while(n&%&i&==&0)&n&/=&i,&phi[j]&*=&i;&&&&&&&&&&&&&&&&}&&&&&&&&&&&&&}&&&&&&&&}&&&&}& & & &这里的phi[i]保存了i这个数的欧拉函数，还是利用素数筛选将所有素数筛选出来，然后针对每个素因子计算它的倍数含有该素因子的个数，利用欧拉公式计算该素因子带来的欧拉函数分量，整个筛选过程可以参考素数筛选。& & & c、欧拉定理和费马小定理& & & 欧拉定理：若n,a为正整数，且n,a互素，则: 。& & & 费马小定理：若p为素数，a为正整数且和p互素，则： 。& & & 由于当n为素数时φ(n) = p-1，可见费马小定理是欧拉定理的特殊形式。& & & 证明随处可见，这里讲一下应用。& & &【例题10】整数a和n互素，求a的k次幂模n，其中k = X^Y, 正整数a,n,X,Y（X,Y&=10^9）为给定值。& & & 问题要求的是a^(X^Y) % n，指数上还是存在指数，需要将指数化简，注意到a和n互素，所以可以利用欧拉定理，令X^Y = kφ(n) + r，那么kφ(n)部分并不需要考虑，问题转化成求r = X^Y % φ(n)，可以采用快速幂取模，二分求解，得到r后再采用快速幂取模求解a^r % n。& & & 5、容斥原理& & & 容斥原理是应用在集合上的，来看图二-5-1，要求图中两个圆的并面积，我们的做法是先将两个圆的面积相加，然后发现相交的部分多加了一次，予以减去；对于图二-5-2的三个圆的并面积，则是先将三个圆的面积相加，然后减去两两相交的部分，而三个圆相交的部分被多减了一次，予以加回。图二-5-1图二-5-2& & &这里的“加”就是“容”，“减”就是“斥”，并且“容”和“斥”总是交替进行的（一个的加上，两个的减去，三个的加上，四个的减去），而且可以推广到n个元素的情况。& & 【例题11】求小于等于m(m & 2^31)并且与n(n & 2^31)互素的数的个数。& & &当m等于n，就是一个简单的欧拉函数求解。& & &但是一般情况m都是不等于n的，所以可以直接摈弃欧拉函数的思路了。& & &考虑将n分解成素数幂的乘积，来看一种最简单的情况，当n为素数的幂即n = p^k时，显然答案等于m - m/p（m/p表示的是p的倍数，去掉p的倍数，则都是和n互素的数了）；然后再来讨论n是两个素数的幂的乘积的情况，即n = p1^k1 * p2^k2，那么我们需要做的就是找到p1的倍数和p2的倍数，并且要减去p1和p2的公公倍数，这个思想其实已经是容斥了，所以这种情况下答案为：m - ( m/p1 + m/p2 - m/(p1*p2) )。& & & 类比两个素因子，如果n分解成s个素因子，也同样可以用容斥原理求解。& & & 容斥原理其实是枚举子集的过程，常见的枚举方法为dfs，也可以采用二进制法（0表示取，1表示不取）。这里给出一版dfs版本的容斥原理的伪代码，用于求解小于等于m且与n互素的数的个数。& &&#define&LL&__int64&&&&void&IncludeExclude(int&depth,&LL&m,&LL&mul,&int&op,&int*&p,&LL&&ans)&{&&&&&&&&if(m&&&mul)&return&;&&&&&&&&&if(depth&==&p[0])&{&&&&&&&&&&&&&ans&+=&(op&?&-1&:&1)&*&(m&/&mul);&&&&&&&&&&&&return&;&&&&&&&&}&&&&&&&&for(int&i&=&0;&i&&&2;&i++)&{&&&&&&&&&&&&&//&0&表示不取,&1表示取&&&&&&&&&&&&IncludeExclude(&depth+1,&m,&mul&*&(i?p[depth+1]:1),&op^i,&p,&ans&);&&&&&&&&}&&&&}& & & p[ 1 : p[0] ]存储的是n的所有素因子，p[0]表示数组长度，mul表示该次的素因子子集的乘积，op表示子集的奇偶性，ans存储最后的答案。& & & 例如求[1, 9]中和6互素的数的个数，这时p = [2, 2, 3] （注意p[0]是存素数的个数的，6分解的素因子为2和3）。& & & ans = 9/1 - （9/2 + 9/3） + 9/6 = 3，ans分为三部分，0个数的组合，1个数的组合，2个数的组合。三、数论常用算法& & & 1、Rabin-Miller 大素数判定& & & 对于一个很大的数n（例如十进制表示有100位），如果还是采用试除法进行判定，时间复杂度必定难以承受，目前比较稳定的大素数判定法是拉宾-米勒（Rabin-Miller）素数判定。& & & 拉宾-米勒判定是基于费马小定理的，即如果一个数p为素数的条件是对于所有和p互素的正整数a满足以下等式：。& & & 然而我们不可能试遍所有和p互素的正整数，这样的话和试除比算法的复杂度反而更高，事实上我们只需要取比p小的几个素数进行测试就行了。& & & 具体判断n是否为素数的算法如下：& & & i) & 如果n==2，返回true；如果 n&2|| !(n&1), 返回false；否则跳到ii)。& & & ii) &令n = m*（2^k） + 1，其中m为奇数，则n-1 = m*（2^k）。& & & iii) 枚举小于n的素数p（至多枚举10个），对每个素数执行费马测试，费马测试如下：计算pre = p^m % n，如果pre等于1，则该测试失效，继续回到iii)测试下一个素数；否则进行k次计算next = pre^2 % n，如果next == 1 && pre ！= 1 && pre != n-1则n必定是合数，直接返回；k次计算结束判断pre的值，如果不等于1，必定是合数。& & & iv) 10次判定完毕，如果n都没有检测出是合数，那么n为素数。& & & 伪代码如下：& &&bool&Rabin_Miller(LL&n)&{&&&&&&&&LL&k&=&0,&m&=&n-1;&&&&&&&&if(n&==&2)&return&true;&&&&&&&&if(n&&&2&||&!(n&&&1))&return&false;&&&&&&&&//&将n-1表示成m*2^k&&&&&&&&while(&!(m&&&1)&)&k++,&m&&&=&1;& & & &&for(int&i&=&0;&i&&&10;&i++)&{&&&&&&&&&&&&&if(p[i]&==&n)&&&&&&&&&&&&&&&&return&true;&&&&&&&&&&&&if(&isRealComposite(p[i],&n,&m,&k)&)&{&&&&&&&&&&&&&&&&return&false;&&&&&&&&&&&&}&&&&&&&&}&&&&&&&&return&true;&&&&}& & & 这里的函数isRealComposite(p, n, m, k)就是费马测试，p^(m*2^k) % n不等于1则n必定为合数，这是根据费马小定理得出的（注意）。n-1 = m*（2^k）& & & isRealComposite实现如下：& &&bool&isRealComposite(LL&p,&LL&n,&LL&m,&LL&k)&{&&&&&&&&LL&pre&=&Power_Mod(p,&m,&n);&&&&&&&&if(pre&==&1)&{&&&&&&&&&&&&return&false;&&&&&&&&}&&&&&&&&while(k--)&{&&&&&&&&&&&&LL&next&=&Product_Mod(pre,&pre,&n);&&&&&&&&&&&&if(next&==&1&&&&pre&!=&1&&&&pre&!=&n-1)&&&&&&&&&&&&&&&&return&true;&&&&&&&&&&&&pre&=&&&&&&&&&}&&&&&&&&return&(&pre&!=&1&);&&&&}& & & 这里Power_Mod(a, b, n)即a^b%n，Product_Mod(a, b, n)即a*b%n，而k次测试的基于费马小定理的一个推论：x^2 % n = 1当n为素数时x的解只有两个，即1和n-1。& & & 2、Pollard-rho 大数因式分解有了大数判素，就会伴随着大数的因式分解，Pollard-rho是一个大数分解的随机算法，能够在O(n ^(1/4) )的时间内找到n的一个素因子p，然后再递归计算n' = n/p，直到n为素数为止，通过这样的方法将n进行素因子分解。 & & & &&& & & Pollard-rho的策略为：从[2, n)中随机选取k个数x1、x2、x3、...、xk，求任意两个数xi、xj的差和n的最大公约数，即d = gcd(xi - xj, n)，如果1 & d & n，则d为n的一个因子，直接返回d即可。& & & 然后来看如何选取这k个数，我们采用生成函数法，令x1 = rand()%(n-1) + 1，xi = （xi-1 ^ 2 + 1 ) mod n，很明显，这个序列是有循环节的，就像图三-2-1那样。图三-2-1& & & 我们需要做的就是在它进入循环的时候及时跳出循环，因为x1是随机选的，x1选的不好可能使得这个算法永远都找不到n的一个范围在(1, n)的因子，这里采用歩进法，保证在进入环的时候直接跳出循环，具体算法伪代码如下：& & LL&Pollard_rho(LL&n)&{&&&&&&&&LL&x&=&rand()&%&(n&-&1)&+&1;&&&&&&&&LL&y&=&x;&&&&&&&&LL&i&=&1,&k&=&2;&&&&&&&&do&{&&&&&&&&&&&&i++;&&&&&&&&&&&&LL&p&=&gcd(n&+&y&-&x,&n);&&&//&这里传入的gcd需要是正数&&&&&&&&&&&&if(1&&&p&&&&p&&&n)&{&&&&&&&&&&&&&&&&return&p;&&&&&&&&&&&&}&&&&&&&&&&&&if(i&==&k)&{&&&&&&&&&&&&&&&&k&&&=&1;&&&&&&&&&&&&&&&&y&=&x;&&&&&&&&&&&&}&&&&&&&&&&&&x&=&Func(x,&n);&&&&&&&&}while(x&!=&y);&&&&&&&&return&n;&&&&}& & & 3、RSA原理& & & RSA算法有三个参数，n、pub、pri，其中n等于两个大素数p和q的乘积(n = p*q)，pub可以任意取，但是要求与(p-1)*(q-1)互素，pub*pri % () = 1 (可以理解为pri是pub的逆元)，那么这里的(n, pub)称为公钥，(n, pri)称为私钥。(p-1)*(q-1)& & & RSA算法的加密和解密是一致的，令x为明文，y为密文，则：& & & 加密：y = x ^ pub % n & &(利用公钥加密，y = encode(x) )& & & 解密：x = y ^ pri % n & & &(利用私钥解密，x = decode(y) )& & & 那么我们来看看这个算法是如何运作的。& & & 假设你得到了一个密文y，并且手上只有公钥，如何得到明文x，从decode的情况来看，只要知道私钥貌似就可以了，而私钥的获取方式只有一个，就是求公钥对(p-1)*(q-1)的逆元，如果(p-1)*(q-1)已知，那么可以利用扩展欧几里德定理进行求解，问题是(p-1)*(q-1)是未知的，但是我们有n = p*q，于是问题归根结底其实是难在了对n进行素因子分解上了，Pollard-rho的分解算法时间 复杂度只能达到O(n ^(1/4) )，对int64范围内的整数可以在几十毫秒内出解，而当n是几百位的大数的时候计算时间就只能用天来衡量了。四、数论题集整理& & & &1、素数和因数分解& & && &★☆☆☆☆& & & & 素数筛选& & &&★☆☆☆☆& & & & 因子数& & && & & & & & & & &&★☆☆☆☆& & & &&因子和& & &&& & & & & &&★☆☆☆☆& & & &&X^Y的因子和& & && & & &&★☆☆☆☆& & & &&循环节的经典问题& & &&& & & & &&★★☆☆☆& & & &&X^Y的因子和& & && & & & & & & & & &★★☆☆☆& & & & 找规律+素数筛选& & &&& & & & & & & & &★★☆☆☆& & & & 整除性质 + 因子枚举& & && & & & &&★★☆☆☆& & & & 3n^2+3n+1 的素数判定问题& & && ★★★☆☆ & & & &因式分解+树状数组+DFS& & && & & & &★★★★☆ & & & &因式分解+线段树& & & &2、GCD && LCM&& & && & &&★☆☆☆☆ & & & &互素判定& & && & & & & &&★★☆☆☆& & & & GCD和LCM性质 + 排列组合& & && & & & &★★☆☆☆& & & & 辗转相除+因子枚举& & &&&★★★☆☆& & & & GCD性质 + 完全背包& & & &3、同余性质 和 循环节& & && & & & & & & &&★☆☆☆☆& & & & 同余的乘法性质& & && & & & & & & &★★☆☆☆ & & & &余数性质& & &★★☆☆☆& & & & 规律& & &&★★☆☆☆& & & & 完全数& & && & & &&★★☆☆☆& & & & 同余性 + 循环节& & && & & & & & &★★★☆☆& & & & 利用同余原理进行动态规划& & &&&★★★★☆& & & & 复杂的循环节& & & &4、模线性方程和逆元& & && & & & & & & &★☆☆☆☆ & & & &线性同余& & && & & & & & & &★☆☆☆☆ & & & &线性同余& & && & & & & & & & &&★★☆☆☆ & & & &逆元& & && && & &★★☆☆☆ & & & &逆元& & &&& & & & & & & & & &★★☆☆☆ & & & &逆元入门题& & && &★★☆☆☆& & & &&同余推导& & &★★☆☆☆& & & &&线性同余+枚举& & && & & & &&★★☆☆☆& & & & 快速幂取模 + 欧几里德定理& & && & & & &&★★★★☆& & & & 树状数组 + 逆元& & & &5、模线性方程组& & &&★★☆☆☆&中国剩余定理 简化版& & &&★★★☆☆&中国剩余定理 模板题& & && & & & & & & & & & &&★★★☆☆&中国剩余定理 模板题& & && & & & & & & & & & & & & &&★★★☆☆&中国剩余定理 模板题& & && & &&&★★★☆☆&中国剩余定理 模板题& & & &6、欧拉函数、欧拉定理、费马小定理& & && & & & & &★☆☆☆☆& & & &费马小定理 简化版的& & && & & & & & & & & &&★☆☆☆☆& & & &欧拉函数& & && & & & & & & & & & &★★☆☆☆& & & &欧拉函数& & && & & & & &★★☆☆☆& & & &筛选法求欧拉函数& & && & &&★★☆☆☆& & & &筛选法求欧拉函数& & && & &★★★☆☆& & & &费马小定理& & && & & & & & &★★★☆☆& & & &费马小定理& & && ★★★☆☆ 费马小定理，我的题& & & &6、容斥原理& & && & & & & & & &&★★☆☆☆& & & &容斥原理& & && & & & & &★★☆☆☆& & & &容斥原理& & && & & & & & & &★★☆☆☆& & & &容斥原理& & && & & & & & & & & & &★★☆☆☆& & & &容斥原理& & && & & & & & & & & & &★★☆☆☆ & & & 容斥原理& & && & & & & & & & &★★★☆☆& & & &二分枚举+容斥原理& & && & & & & & & &&★★★☆☆ & & & 容斥原理& & & &7、大素数判定& & && & & &★★★☆☆ & & & 拉宾米勒大数判素+dfs& & && & &★★★☆☆ & & & 拉宾米勒& & && & & &★★★★☆& & & &拉宾米勒& & && & & & & & &&★★★★☆ & & &&拉宾米勒+Pollard-rho& & && & & & & & & & & & &★★★★☆ & & &&拉宾米勒 + 线性同余& & & &8、离散对数-Baby Step Gaint Step算法& & && & & &&★★★☆☆ & & & 基础& & && & & & & & & &&★★★★☆ & & & 扩展Baby Step Giant Step& & && & & & & &★★★★★& & & &Baby Step Giant Step&+ 高斯消元& & & &9、其它& & &&&& & &&& & && & &&&& & && & &&& & && & && & && & && & && & && & && & && & &
&re: 夜深人静写算法（五） - 初等数论&&&&
C找循环节求递推式可以，也可以构造矩阵直接用矩阵快速幂啊~