安u

分类

题解(5)

/ 注册

全部文章（共5篇）

（牛客第四场）子段乘积（尺取法、拓展欧几里得算法、矩阵快速幂、逆元、费马小定理）

（牛客第四场）子段乘积（尺取法、拓展欧几里得算法、矩阵快速幂、逆元、费马小定理）链接给出长度为n的数列，求其长度为k的连续字段的乘积对取模余数的最大值。先看几个预备知识：拓展欧几里得算法：对于，一定有一组整数解。利用数学归纳法证明： ①当b=0时，y=0，x=1，显然成立。 ②假设成立，那...

费马小定理快速幂逆元尺取法拓展欧几里得算法

2020-02-12

8 793

(牛客第二场) E.做计数(数学)

(牛客第二场) E.做计数(数学) 链接求有多少不同的正整数三元组，满足，且。两边平方得：由于都为正整数，显然也为正整数，为完全平方数。我们可以枚举所有的，使其乘积为完全平方数即可。 #include <cstdio> #include <cmath> using ...

2020-02-12

0 843

（牛客第二场）G.判正误(快速幂)

（牛客第二场）G.判正误(快速幂) 链接有七个整数a,b,c,d,e,f,g，并且猜想。请验证猜想是否成立。利用快速幂，可以很方便求出，,,,取模后加上看它是否等于g。为了防止数据中出现对mod取模和对mod取模的结果相等，然而它们的值不相等的情况，可以多取几个质数的模，逐个来试，绕过所有数据，...

2020-02-12

0 824

E.rin和快速迭代（约数，模拟）

(牛客第一场)E.rin和快速迭代链接设为的因子个数，将迭代下去，任意正整数都会变成2。对于一个比较大的数而言，它的因子数，通常远远小于这个数本身，所以暴力求解时间复杂度也不高，迭代几次往往就能求出答案。 #include <iostream> #include <cmat...

2020-02-12

0 793

J.u's的影响力(矩阵快速幂，费马小定理)

（牛客第一场）J.u's的影响力(矩阵快速幂，费马小定理) 第一天的影响力为，第二天的影响力为，从第三天开始，每一天的影响力为前两天的影响力的乘积再乘以的次方。用数学语言描述：。输出第n天的影响力，对1e9+7取模。由于，所以用快速幂。先推几个公式，找规律：从第三项开始x的幂次为1,1,2,3...

费马小定理快速幂矩阵快速幂

2020-02-12

8 1104