（牛客第四场）子段乘积（尺取法、拓展欧几里得算法、矩阵快速幂、逆元、费马小定理） 链接 给出长度为n的数列，求其长度为k的连续字段的乘积对取模余数的最大值。 先看几个预备知识： 拓展欧几里得算法：对于，一定有一组整数解。 利用数学归纳法证明： ①当b=0时，y=0，x=1，显然成立。 ②假设成立，那么对于也成立。 ③假设存在解使得。 ④需要证明存在解。 令，。 移项得：。将其代入要证明的式子得:$x_1=y_2,y_1=(x_2-k*y_2)$就行了。 模板: void ext_gcd(int a,int b,int &d,int &x,int &y){ if(...

(牛客第二场) E.做计数(数学) 链接 求有多少不同的正整数三元组，满足，且。 两边平方得： 由于都为正整数，显然也为正整数，为完全平方数。 我们可以枚举所有的，使其乘积为完全平方数即可。 #include <cstdio> #include <cmath> using namespace std; int main(){ int n; scanf("%d",&n); int ans=0; for(int i=1;i<=sqrt(n);i++){ //枚举n以内的完全平方数 int k=i*i; ...

（牛客第二场）G.判正误(快速幂) 链接有七个整数a,b,c,d,e,f,g，并且猜想。请验证猜想是否成立。 利用快速幂，可以很方便求出，,,,取模后加上看它是否等于g。 为了防止数据中出现对mod取模和对mod取模的结果相等，然而它们的值不相等的情况，可以多取几个质数的模，逐个来试，绕过所有数据，我选了一个1e9+7就过了。 #include <cstdio> #include <algorithm> #include <string> #include <iostream> const int maxn=1000000007; using n...

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

（牛客第一场）J.u's的影响力(矩阵快速幂，费马小定理) 第一天的影响力为，第二天的影响力为，从第三天开始，每一天的影响力为前两天的影响力的乘积再乘以的次方。用数学语言描述：。输出第n天的影响力，对1e9+7取模。 由于，所以用快速幂。 先推几个公式，找规律： 从第三项开始x的幂次为1,1,2,3,5...是斐波那契数列 的幂次为是斐波那契数列 的幂次为不是斐波那契数列，但为前两项之和+1 同时还需用到一个数论的结论：费马小定理。 费马小定理：为素数，对于任意整数都有。 若无法被整除，则有。 根据费马小定理，我们可以通过矩阵快速幂求得逆元，因为由上式有，不过跟这题没关系。 矩阵快速幂求斐波那...