wxyww

未归档

精品(28) 题解(65)

/ 注册

全部文章 / 未归档（共302篇）

矩阵快速幂优化菲波那切数列

　　普通的斐波那契数列的递推式很简单，但是如果要求第1014个斐波那契数的话，肯定会tle，这时就可以用矩阵快速幂来优化。　　菲波那切数列普通的递推式是　　f[i]=f[i-1]+f[i-2] 　　而矩阵乘法的规则是，讲n行m列的矩阵与k行n列的矩阵相乘，所得矩阵的第i行第j列的数是由第一...

数论

2018-07-06

0 468

矩阵快速幂优化菲波那切数列

　　普通的斐波那契数列的递推式很简单，但是如果要求第1014个斐波那契数的话，肯定会tle，这时就可以用矩阵快速幂来优化。　　菲波那切数列普通的递推式是　　f[i]=f[i-1]+f[i-2] 　　而矩阵乘法的规则是，讲n行m列的矩阵与k行n列的矩阵相乘，所得矩阵的第i行第j列的数是由第一...

数论

2018-07-06

0 508

快速幂&快速乘法

尽管快速幂与快速乘法好像扯不上什么关系，但是东西不是很多，就一起整理到这里吧快速幂思想就是将ax看作x个a相乘，用now记录当前答案，然后将指数每次除以2，然后将当前答案平方，如果x的2进制最后一位为1的话，就将答案乘以现在的数。快速乘法类似，只是将a*x看作x个a相加。代码　　 ...

数论

2018-07-06

0 422

快速幂&快速乘法

尽管快速幂与快速乘法好像扯不上什么关系，但是东西不是很多，就一起整理到这里吧快速幂思想就是将ax看作x个a相乘，用now记录当前答案，然后将指数每次除以2，然后将当前答案平方，如果x的2进制最后一位为1的话，就将答案乘以现在的数。快速乘法类似，只是将a*x看作x个a相加。代码　　 ...

数论

2018-07-06

0 496

筛法

有两种筛法，第一种叫做埃拉托斯特尼筛法（复杂度O(n log logn)），另一种是欧拉筛法（复杂度O(n)）埃拉托斯特尼筛法其实就是用已得到质数，去将他的所有n以内倍数标记为合数，最后剩下的就是合数。在进行筛法的同时，可以顺便找到每个数的最小质因数（就是第一次更新他的那个质数）欧...

数论

2018-07-06

0 518

筛法

有两种筛法，第一种叫做埃拉托斯特尼筛法（复杂度O(n log logn)），另一种是欧拉筛法（复杂度O(n)）埃拉托斯特尼筛法其实就是用已得到质数，去将他的所有n以内倍数标记为合数，最后剩下的就是合数。在进行筛法的同时，可以顺便找到每个数的最小质因数（就是第一次更新他的那个质数）欧...

数论

2018-07-06

0 476

费马定理&欧拉定理

费马定理: ap≡a(mod p) 其中p为质数，且a不是p的倍数证明：。。。。。欧拉定理： aφ（p）≡1(mod p) φ（x）（欧拉函数）为小于等于x且与x互质的数的个数 φ（x）=∏（pi-1）*piki-1 其中pi表示 x的质因数，ki表示这种质因数的个数 ...

数论

2018-07-06

0 491

费马定理&欧拉定理

费马定理: ap≡a(mod p) 其中p为质数，且a不是p的倍数证明：。。。。。欧拉定理： aφ（p）≡1(mod p) φ（x）（欧拉函数）为小于等于x且与x互质的数的个数 φ（x）=∏（pi-1）*piki-1 其中pi表示 x的质因数，ki表示这种质因数的个数 ...

数论

2018-07-06

0 490

逆元&欧拉函数

欧拉函数：　　φ(p)表示小于p的正整数中与p互质的数的个数，称作欧拉函数。　　求单个数的欧拉函数时可以利用来求　　其中pi为p分解出的质因数，ki表示该质因数的指数　　代码： #include<cstdio> #include<iostre...

数论

2018-06-15

0 509

逆元&欧拉函数

欧拉函数：　　φ(p)表示小于p的正整数中与p互质的数的个数，称作欧拉函数。　　求单个数的欧拉函数时可以利用来求　　其中pi为p分解出的质因数，ki表示该质因数的指数　　代码： #include<cstdio> #include<iostre...

数论

2018-06-15

0 0