青烟绕指柔

数论

2-SAT(1) bfs(6) Codeforces(3) dfs(4) Hash(1) HDU(2) KM(1) LCA(2) Link_Cut_Tree(1) LIS(1) Splay(1) STL(7) WQS二分(1) 中等难度(6) 主席树(4) 二分(1) 分块(1) 前缀和(1) 动态规划(15) 博弈论(1) 双连通分量(1) 图论(158) 堆(3) 字符串(5) 差分(1) 并查集(13) 拓扑排序(4) 数位dp(3) 数学(1) 无旋treap(2) 最小环(2) 最小生成树(11) 最短路(18) 树形dp(1) 树状数组(16) 树结构(4) 树链剖分(1) 概率dp(2) 相对大小问题(1) 矩阵乘法(3) 离线算法(12) 线性基(2) 线段树(28) 背包问题(2) 莫队(1) 计算几何(8) 贪心(2) 距离表示(1) 题解(4)

/ 注册

全部文章 / 数论（共12篇）

卡特兰数

卡特兰数是组合数学中，很经典的一类问题，一般可以解决一下问题 n个左括号和n个右括号组成的合法括号序列的数量为 Cat(n); 1,2，3，……，n 经过一个栈，形成的合法出栈序列的数量为 Cat(n); n 个节点构成的不同二叉树的数量为 Cat(n); 在平面直角坐标系上，每...

2019-12-27

1 658

同余方程

线性同余方程,也就是给定a,b,m,求一个整数x满足a*x≡b(mod m)a*x≡b(mod m),然后因为ax≡b(mod m)ax≡b(mod m)等价于 ax−b是m的倍数,不妨设y为一个负数,那么这个方程可以改写为ax+m*y=b 于是我们可以通过拓展欧几里得算法求出特解,然后(x%...

2019-12-27

0 556

计算系数

给定一个多项式(ax+by)k,请求出多项式展开后x^n * y^m项的系数。输入格式共一行，包含 5 个整数，分别为 a，b，k，n，m，每两个整数之间用一个空格隔开。输出格式输出共 1 行，包含一个整数，表示所求的系数，这个系数可能很大，输出对10007 取模后的结果。数据范围 ...

2019-12-27

0 471

O(1)快速乘

求两个数相乘并取模，但是乘积超过了long long怎么办呢？一般都是快速幂的思想快速乘，时间复杂度为log(n)很快了，这里提供一个更快的O(1)算法 inline long long multi(long long x,long long y,long long mod) { long ...

2019-12-27

0 516

欧拉降幂

一般对于 a^b%p 的形式当b很大，大到long long都存不小时，就不能直接快速幂了，必须对b取模，但不是直接让b对p取模，为什么呢？因为是错的。这个时候我们怎么办呢？这个时候我们就要用到欧拉降幂了。上面就是欧拉降幂的公式，一般来说，我们使用第三个即可。 phi 就是欧拉函数。...

2019-12-27

0 495

斐波那契数列的各自性质

gcd( F [ n + 1 ] , F [ n ] ) = 1 gcd(f[n],f[m]) = f[gcd(n,m)] 　　1.f(0)+f(1)+f(2)+…+f(n)=f(n+2)-1。　　可以用于斐波那契数列求前缀和，然后在用矩阵快速幂求出答案。　　2.f(1)+f(3)+f(...

2019-12-27

0 709

hdu 2588

看到这道题，首先应该就想到了求因子，但是计算的时候，又会有重复，就很麻烦，所以我们需要素数这个东西。问题所要求的是 gcd( x , n ) > m ,由gcd( x , n )本身可知，gcd求出来的是 x 和n的最大公约数（设为a），即有式子gcd( x ,n )=a , 进一步进行化...

2019-12-27

1 458

poj 2142

Ms. Iyo Kiffa-Australis has a balance and only two kinds of weights to measure a dose of medicine. For example, to measure 200mg of aspirin using 300m...

2019-12-27

0 672

错排问题

先给出百度百科的概念： n个有序的元素应有n!个不同的排列，如若一个排列使得所有的元素不在原来的位置上，则称这个排列为错排；有的叫重排。错排数怎么计算呢？ n 的错排数我们用 D[n] 来表示: 第一步，考虑第n个元素，把它放在某一个位置，比如位置k，一共有n-1种放法；第二步，考虑第k...

2019-12-27

0 972

三分求函数极值

这篇博客是个极其简单的东西。如题，给出一个N次函数，保证在范围[l,r]内存在一点x，使得[l,x]上单调增，[x,r]上单调减。试求出x的值。输入格式第一行一次包含一个正整数N和两个实数l、r，含义如题目描述所示。第二行包含N+1个实数，从高到低依次表示该N次函数各项的系数。输出...

2019-12-27

0 494