标签:数论

【题解】 「CodePlus 2017 12 月赛」可做题2 线性同余方程 LOJ – 6257

1. 题目

传送门= ̄ω ̄=

2. 题解

居然比赛的时候想出来正解了。

设广义斐波那契数列:$A$,第$i$项为$A_i$

设“狭义”(一般)斐波那契:$Fib$,第$i$项为$Fib_i$[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】 组合数问题 动态规划 NOIP 2016 LUOGU – 2822

1. 题目

传送门= ̄ω ̄=

2. 题解

感觉自己noip2016在仙游。。。
为什么这么水的题目没想出来?当时也学了组合数递推求$C_n^k$
先预处理出$C_n^k\ mod\[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【算法】 非矩阵方法log2N计算斐波那契数列第N项

一些废话

定义斐波那契数列为:
\begin{equation}
\begin{cases}
Fib(1)=1 \\
Fib(2)=1 \\[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】 Biorhythms 中国剩余定理 HDU – 1370

一看这题目名字就想起了——βίος

1. 题目

传送门= ̄ω ̄=

2. 题解

中国剩余定理模板题(甚至还简单些)(也许蒟蒻窝只做得动这种题了)
设下一次发生的时间是s
可以得到:
$$s [......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【算法】 BSGS算法

废话

BSGS算法,即Baby Steps Giant Steps,又名大小步算法。
拔山盖世算法、北上广深算法
是一中基础的数论算法

问题

给出a,b,p三个整数,其中p为素数,求一个未知数x[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】余数之和 数论 分块优化 [CQOI2007] BZOJ – 1257

1. 题目

传送门= ̄ω ̄=

题意:
给出n,k,求:
$$\sum_{i=1}^{n}k\ mod\ i$$
$$n,k\in [1,10^9]$$

2. 题解

以我这智障脑[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【算法】组合数的各种性质和定理 –litble

从m个物品里选出n个的方案数,记作$C_m^n$,即为组合数
组合数有很多很多的性质和定理。。。
注意由于本人沉迷玩梗无法自拔,如果看见您看不懂的梗请随意跳过。

组合数通项公式

$$C_m^n=\[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】傻牛的递推数列的另类证明 -boshi

题意:

求f(1)=f(2)=1的斐波那契数列中f(i)|f(x)的i之和

分析:

首先,我们发现一个规律:
比如在mod 8 意义下,斐波那契数列是这样的:
(1 1 2 3 5 0 5 5[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【题解】傻牛的递推数列–litble

题目描述

傻牛最近钻研各类数学递推数列。尤其是斐波那契数列。
傻牛眼中的斐波那契数列是这样的,F1=1,F2=1,然后Fi+2=Fi+1 + Fi,逐项递推。
今天,傻牛发现,某些斐波那契项之间是成[......]

[继续阅读= ̄ω ̄=]

Read MoreComment

【算法】求逆元方法总结 -boshi

引理:

缩系:

简单的定义:对于m(m>1),在[1,m]区间中所有与m互素的数可以构成一个缩系。
缩系性质1、缩系中必定每个元素都有自己唯一的逆元,并且每个元素的逆元不与其他元素的重复(一一对应的[......]

[继续阅读= ̄ω ̄=]

Read MoreView 9 Comments