wxyww

分类

未归档(12) 精品(28) 题解(65)

/ 注册

全部文章（共22篇）

[luoguU42591][小T的面试题]

luoguU42591 题意： n个不超过n的正整数中,其中有一个数出现了两次,其余的数都只出现了一次, 求这个出现两次的数。思路：这个题的亮点在于内存限制1MB。明显不能再用数组储存了，肯定是用一些运算来求出那个数。假设出现两次的数为x，没有出现的数为y。一开始很容易想到计算出1到n加...

数论

2018-10-05

0 462

逆元&欧拉函数

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

数论

2018-06-15

0 509

高斯消元法

高斯消元法可以用于求解线性方程组，即n元1次方程组。利用矩阵，大致思路与普通解方程方法类似。只是更具一般性。将系数与右侧的常数存成一个矩阵，然后每次用第i行消去下面每行的第i个系数，最后就会得到一个一元方程，然后从后到前依次代回即可。　　然后就是精度的问题，因为计算机中没有分数，所以只能用d...

数论

2018-05-19

0 443

费马定理&欧拉定理

费马定理: 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

筛法

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

数论

2018-07-06

0 518

快速幂&快速乘法

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

数论

2018-07-06

0 422

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

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

数论

2018-07-06

0 468

关于gcd的四道题

T1:bzoj2705 题目描述：给定一个n求\(\sum\limits_{i=1}^ngcd(i,n)\) 因为n太大，所以O(n)的做法肯定不行，然后就去想根号的方法。 \[\sum\limits_{i=1}^{n}gcd(i,n)\]\[=\sum\limits_{k|n}k*\su...

数论

2018-08-25

0 393

数论基础

基础数论快速幂：用来快速求m的n次幂，并取模矩阵乘法：当且仅当前一个矩阵的列数等于第二个矩阵的行数时，可以进行矩阵乘法，矩阵乘法不满***换律，满足结合律.\[C_{ij}=\sum\limits_{k=1}^n{A_{ik}*B_{kj}}\] 方阵可以进行矩阵快速幂。单位矩阵的...

数论

2018-08-20

0 486

[luogu2822][组合数问题]

题目链接题解: 对于上面和下面的式子进行分解质因数，然后看看上面的质因数个数减去下面的质因数个数能不能达到k的质因数的要求即可。分解质因数的时候用对于阶乘分解质因数的常用方法:比如要求1999！中能分解出多少个5，那么就把1999不断的除以5，并且把得到的数相加即可。原因显然。但是上面...

数论

2018-08-25

0 512