三木成森

数论

ac自动机(1) codeforces(1) 前缀和(2) 后缀(1) 图论(1) 字符串(2) 数据结构(4) 神奇的c++(2) 自动机(1)

/ 注册

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

斐波那契自卷积

牛客挑战赛32 C 不会推导，贴一个oeis链接https://oeis.org/A001629通过链接我们知道: 这样我们就可以通过矩阵快速幂求解代码 #include <bits/stdc++.h> using namespace std; typedef long long l...

2019-09-21

0 398

数论分块——学习

引子现有一公式，求 a n s = ...

2019-09-18

0 407

二次剩余－学习

二次剩余形如: x 2 ≡ d ...

2019-08-19

0 319

二分递归求等比数列前n项和

2019河北省大学生程序设计竞赛（重现赛）Ｂ我们假设有一个等比数列: a[n] = q ^ n 那么 S[n] = q ^ 1 + q ^ 2 + q ^ 3 …… + q ^ n 正常情况我们有 S[n] = q * (1 - q ^ n) / (1 - q) 若我们需要求的是 S[n] % m...

2019-05-25

0 459

快速幂

理解一般的我们求a^b可以跑一个for或者pow函数，这种在遇到大的数据范围很浪费时间或者存不下。这时候就可以使用快速幂进行求解快速幂快速幂使用了二进制的思想，假如b=11 二进制 1011 快速幂的作用就是给1与1之间的距离缩短了 int p_pow(int a,int b,int...

数论

2018-11-26

0 345

唯一分解定理

简介唯一分解定理是数论中重要的思想之一。简述就是一个大于一的整数N,可以由他的素因子唯一构成。证明用到了反证法。数学假设N是大于一的正整数，我们有： N=q1^p1*q2^p2*……*qn^pn q1……qn是N的质因数有如下性质： 1. 约数个数 = (p1+1)*(p2+...

2018-11-26

0 303

素数筛

##素数## 素数即质数，只能被自身和一整除。一般暴力找素数，O(n2)或者O(nsqrt(n)) 这样耗费时间太多，所以我们用筛法来处理 ##素数筛## 素数筛通过将非素数筛掉来找素数，是重要的数论工具 ###一般筛法### --埃氏筛一般筛法接近O（n）的复杂度，但比快速筛慢 bool m...

数论素数

2018-08-30

0 293