Transient~

数论

Android(14) c语言基础算法(2) dfs(1) dp(6) Java学习(1) 图论(5) 数据结构(4) 未归档(1) 贪心(1)

/ 注册

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

【数论基础】- 素数筛

两种素数筛法引言：唯一分解定理：算术基本定理可表述为：任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积N=P1a1P2a2P3a3…Pnan，这里P1<P2<P3…<Pn均为质数，其中指数ai是正整数。这样的分解称为 N 的标准分解式。 **思...

2020-01-02

0 512

【数论基础】- 扩展欧几里得

扩展欧几里得定义：扩展欧几里得算法是欧几里得算法（又叫辗转相除法）的扩展。除了计算a、b两个整数的最大公约数，此算法还能找到整数x、y（其中一个很可能是负数）。通常谈到最大公因子时, 我们都会提到一个非常基本的事实: 给予二整数 a 与 b, 必存在有整数 x 与 y 使得ax + by = ...

2020-01-02

0 598

【矩阵快速幂】- 洛谷 p3390 模板题（补一道斐波那契数列）

矩阵快速幂大意：就是对矩阵求快速幂，将快速幂中res=1换成单位阵，而取模运算完全在我们定义的乘法运算中进行，即Mul，其他的跟快速幂没有区别，当然我现在只掌握了基础，所以做了一道模板题。题目描述：题目链接：洛谷-p3390 题目背景矩阵快速幂题目描述给定n*n的矩阵A，求A^k...

2020-01-02

0 804

poj - 2142 超详细解释数论【扩展欧几里得】

扩展欧几里得题目链接：The Balance 题目描述： Description Ms. Iyo Kiffa-Australis has a balance and only two kinds of weights to measure a dose of medicine. For exa...

2020-01-02

0 533

【数论基础】- 欧拉函数

什么是欧拉函数定义：在数论，对正整数n，欧拉函数是小于n的正整数中与n互质的数的数目（φ(1)=1）。此函数以其首名研究者欧拉命名(Euler’s totient function)，它又称为Euler’s totient function、φ函数、欧拉商数等。例如φ(8)=4，因为1,3,...

2020-01-02

0 967

【数论基础】- 欧拉降幂和卢卡斯定理

欧拉降幂公式：例题： poweroj - 2366 题目描述：题意：计算ab的c次幂 %1000000007。输入：a，b，c。输出：取模后的结果。分析：这道题就是一个板子，直接套公式，只不过有两层。直接完全套公式…很暴力。代码： #include<stdio.h>...

2020-01-02

0 467

循环节 - 【数论】

循环节引言：小学的规律题大家不陌生吧，经常跟取余数挂钩的那种，其实挺简单的。比如给你一个序列1 3 5 7 9 1 3 5 7 9 1 3 …这就是小学题目嘛，对吧看着好简单。循环节：其实现在很多题目也要用到同样的方法，打表找出循环节点，然后再去处理它。这类题目往往有些特点，数据大，结果取...

2020-01-02

0 447