数论小专题——因数的分解
一、大整数质数探测 Miller_rabin算法
p" role="presentation">ppp是质数，费马小定理 ap−1=1(mod p)" role="presentation">ap−1=1(mod p)ap−1=1(mod p)a^{p-1}=1(mod\ p)
p​" role="presentation">ppp是质数，x2=1(mod p)→x=1 or

1、快速莫比乌斯变换
1.1 什么是莫比乌斯变换
快速莫比乌斯变换，简称(FMT)，也是一种对数列的变换。类似FFT地，FMT也是通过将数列/多项式在两种形式下来回变换达到加速两个数列/多项式卷积的效果。
FFT解决的是这样的卷积：
Cx=∑i+j=xaibj" role="presentation" style="position: relative;">Cx=∑i+j=xaibjCx=∑i+j=xaibj C_x=\sum_{i+j=x}a_ib_j
其中x,i,j" role="presentation" style=
? 原创 ?
2018-11-13 09:25:17
658
0
0
原来一直只把调和级数(Hn" role="presentation" style="position: relative;">HnHnH_n)当成算复杂度的工具。
直到遇到了这样一道题：
T2062 随机数生成器
通过打表可以发现，答案就是Hn+1" role="presentation" style="position: relative;">Hn+1Hn+1H_n+1
但是n" role="presentation" style="position: relative;">nnn太大，调和数本身也没有通项公式。
在说这道题之前，我们先来说说调和数是什么吧
? 原创 ?
2018-03-14 20:00:11
314
1
1
pdf以及std：难题选讲2.zip
引言：有一类数据结构题型略微奇妙，下面是一个例子。
CF259 Div1 E. Little Pony and Lord Tirek
时间限制:3000ms|空间限制:256MB
半人马提雷克是“我的小马驹：友谊是魔法”第四季最后两集的大反派。在“闪闪王国（上）”中，提雷克从塔他洛斯逃了出来。为了变得更加强大，他还吸取了小马们的魔法。
提雷克的核心技能是法力吸取。这个技能可以吸收一个魔法生物的所有魔力并把它们交给施法者。
现在我们把这个问题简化，假设你有n只小马（编号从1到n）。每只小马有三种属性。
si：时间为0时这只小马拥有
? 原创 ?
2018-03-13 13:39:01
301
0
0
PDF以及配套数据下载地址：难题选讲2-送你一公式数论-Rockdu.rar
引言：有一类数论问题，考察数学公式的灵活运用与变换。我们来看一个例子：
最小公倍数之和 V3
时空限制：1s / 256MB
出一个数N，输出小于等于N的所有数，两两之间的最小公倍数之和。
相当于计算这段程序（程序中的lcm(i,j)表示i与j的最小公倍数）：
由于结果很大，输出Mod 1000000007的结果。
G=0;for(i=1;i< N;i++)for(j=1;j<=N;j++){ G = (G + lcm(i,j)) % 1000000007;}
? 原创 ?
2018-01-26 17:50:39
202
0
0
PDF以及配套数据下载地址：难题选讲1-送你一序列字符串-Rockdu.rar
浅谈一类字符串问题
引言：有一类不常规的序列上字符串问题十分的特别。下面我们来看一个例子。
所有公共子序列问题V2
时空限制：1s/256MB
题目描述：
给定长度分别为n, m的只包含小写字母的串A, B。你需要输出A、B所有本质不同的公共(或公共回文)子序列的个数，答案对66662333取模。详见数据范围。（空序列算作回文序列）
输入格式：
一行n, m, k, k作为子问题标识
第二行长度为n的字符串，表示A
另一行长度为m的字符串，表示B
泰勒展开-皮亚诺余项:
*本文中f(i)都指f的i阶导数" role="presentation" style="position: relative;">f(i)都指f的i阶导数f(i)都指f的i阶导数f^{(i)}都指f的i阶导数
f(x)=(∑i=0∞f(i)(x0)(x−x0)ii!)+o[(x−x0)∞],o[(x−
Rockdu's Blog