BZOJ_5118_Fib数列2_矩阵乘法+欧拉定理
BZOJ_5118_Fib数列2_矩阵乘法+欧拉定理DescriptionFib定义为Fib(0)=0,Fib(1)=1,对于n≥2,Fib(n)=Fib(n-1)+Fib(n-2)现给出N，求Fib(2^n).Input本题有多组数据。第一行一个整数T，表示数据组数。接下来T行每行一个整数N，含义...
URAL 1141. RSA Attack（欧拉定理+扩展欧几里得+快速幂模）
题目链接题意 ： 给你n，e，c，并且知道me ≡ c (mod n)，而且n = p*q，pq都为素数。思路 ： 这道题的确与题目名字很相符，是个RSA算法，目前地球上最重要的加密算法。RSA算法原理 。看到这个算法之后，就知道这个题是求cd≡m(mod n),要求m，就要先求d，而d则是e的模反...
数学基础IV 欧拉函数 Miller Rabin Pollard's rho 欧拉定理 行列式
找了一些曾经没提到的算法。这应该是数学基础系最后一篇。曾经的文章：数学基础I莫比乌斯反演I莫比乌斯反演II数学基础II生成函数数学基础III博弈论容斥原理（hidden）线性基（hidden）卡特兰数/第二类斯特林数（hidden）置换群（hidden）莫比乌斯反演III（hidden）线性筛（hi...
洛谷 P2480 [SDOI2010]古代猪文 题解【欧拉定理】【CRT】【Lucas定理】
数论综合题。题目背景题目背景与题目无关因此省略。题目链接题目描述猪王国的文明源远流长，博大精深。iPig在大肥猪学校图书馆中查阅资料，得知远古时期猪文文字总个数为\(N\)。当然，一种语言如果字数很多，字典也相应会很大。当时的猪王国国王考虑到如果修一本字典，规模有可能远远超过康熙字典，花费的猪力、物...
2018牛客网暑期ACM多校训练营（第四场） A - Ternary String - [欧拉降幂公式][扩展欧拉定理]
题目链接：https://www.nowcoder.com/acm/contest/142/A题目描述Aternarystringisasequenceofdigits,whereeachdigitiseither0,1,or2.Chiakihasaternarystringswhichcansel...
数论的欧拉定理证明 & 欧拉函数公式(转载)
欧拉函数：欧拉函数是数论中很重要的一个函数，欧拉函数是指：对于一个正整数n，小于n且和n互质的正整数（包括1）的个数，记作φ(n)。完全余数集合：定义小于n且和n互质的数构成的集合为Zn，称呼这个集合为n的完全余数集合。显然|Zn|＝φ(n)。有关性质：对于素数p，φ(p)=p-1。对于两个不同素数...