搜索结果
查询Tags标签： 逆元，共有 29条记录-
2020第一届辽宁省赛E.线段树 ——exgcd + 逆元 + 线段树
题目链接 题意： 中文题 思路： 题目要求维护区间两两数的乘积，可以转化为维护区间的平方和。 需要用到逆元 // Decline is inevitable, // Romance will last forever. //#include <bits/stdc++.h> #include <iostream> #include <cmath> #include &l…
2021/10/19 23:11:52 人评论 次浏览 -
2020第一届辽宁省赛E.线段树 ——exgcd + 逆元 + 线段树
题目链接 题意： 中文题 思路： 题目要求维护区间两两数的乘积，可以转化为维护区间的平方和。 需要用到逆元 // Decline is inevitable, // Romance will last forever. //#include <bits/stdc++.h> #include <iostream> #include <cmath> #include &l…
2021/10/19 23:11:52 人评论 次浏览 -
关于求 1~n 逆元
以下 \(p\) 为模数，\(x\) 为我们要求逆元的数。 最直接的是利用费马小定理，\(x^{-1}\equiv x^{p-2}(mod\ p)\)是，时间复杂度：\(\mathcal {O}(nlog_2(n))\)。 这里有两个线性做法：令 \(p=ax+b\)，则 \(ax+b\equiv 0(mod\ p)\)，构造一下，两边同时除以 \(bx\)。 则 \(…
2021/8/14 6:07:27 人评论 次浏览 -
关于求 1~n 逆元
以下 \(p\) 为模数，\(x\) 为我们要求逆元的数。 最直接的是利用费马小定理，\(x^{-1}\equiv x^{p-2}(mod\ p)\)是，时间复杂度：\(\mathcal {O}(nlog_2(n))\)。 这里有两个线性做法：令 \(p=ax+b\)，则 \(ax+b\equiv 0(mod\ p)\)，构造一下，两边同时除以 \(bx\)。 则 \(…
2021/8/14 6:07:27 人评论 次浏览 -
欧拉函数和逆元
欧拉函数 定义 欧拉函数表示 再[1,n-1],这个闭区间中和n互质的的数字的个数。 通式 φ(x)=x* (1-1/p1)* (1-1/p2)* (1-1/p3)* (1-1/p4)……(1-1/pn) 性质 若n为质数 有 phi[n]=n-1当a，b互质时，phi[a*b]=phi[a]*phi[b](a,b 不一定是质数)当p是质数，n=kp时，phi[n*p]=phi…
2021/8/6 23:09:37 人评论 次浏览 -
欧拉函数和逆元
欧拉函数 定义 欧拉函数表示 再[1,n-1],这个闭区间中和n互质的的数字的个数。 通式 φ(x)=x* (1-1/p1)* (1-1/p2)* (1-1/p3)* (1-1/p4)……(1-1/pn) 性质 若n为质数 有 phi[n]=n-1当a，b互质时，phi[a*b]=phi[a]*phi[b](a,b 不一定是质数)当p是质数，n=kp时，phi[n*p]=phi…
2021/8/6 23:09:37 人评论 次浏览 -
快速幂求逆元（C++）
题目 输入样例： 3 4 3 8 5 6 3输出样例： 1 2 impossible 代码 #include<iostream>using namespace std;typedef long long LL;int qmi(int a, int b, int p) {int res = 1;while(b){if(b & 1) res = (LL) res * a % p;b >>= 1;a = (LL) a * a % p;}ret…
2021/7/23 22:17:48 人评论 次浏览 -
快速幂求逆元（C++）
题目 输入样例： 3 4 3 8 5 6 3输出样例： 1 2 impossible 代码 #include<iostream>using namespace std;typedef long long LL;int qmi(int a, int b, int p) {int res = 1;while(b){if(b & 1) res = (LL) res * a % p;b >>= 1;a = (LL) a * a % p;}ret…
2021/7/23 22:17:48 人评论 次浏览 -
扩展欧几里得求乘法逆元
在开始之前我们先介绍3个定理： 1.乘法逆元（在维基百科中也叫倒数，当然是 mod p后的,其实就是倒数不是吗？）: 如果ax≡1 (mod p),且gcd(a,p)=1（a与p互质），则称a关于模p的乘法逆元为x。 2.费马小定理（定义来自维基百科）： 假如a是一个整数，p是一个质数，而整数a不…
2021/7/13 6:05:51 人评论 次浏览 -
扩展欧几里得求乘法逆元
在开始之前我们先介绍3个定理： 1.乘法逆元（在维基百科中也叫倒数，当然是 mod p后的,其实就是倒数不是吗？）: 如果ax≡1 (mod p),且gcd(a,p)=1（a与p互质），则称a关于模p的乘法逆元为x。 2.费马小定理（定义来自维基百科）： 假如a是一个整数，p是一个质数，而整数a不…
2021/7/13 6:05:51 人评论 次浏览 -
AcWing 876. 快速幂求逆元
题目链接 ：点击查看 题目描述 ： 给定 n 组 ai,pi，其中 pi 是质数，求 ai 模 pi 的乘法逆元，若逆元不存在则输出 impossible。注意：请返回在 0∼p−1 之间的逆元。乘法逆元的定义若整数 b，m 互质，并且对于任意的整数 a，如果满足 b|a，则存在一个整数 x，使得 a/b≡…
2021/6/14 10:52:26 人评论 次浏览 -
算法学习(10)：乘法逆元
逆元 扩展欧几里得 void exgcd(int a, int b, int& x, int& y) {if (b == 0) {x = 1, y = 0;return;}exgcd(b, a % b, y, x);y -= a / b * x; }快速幂 inline int qpow(long long a, int b) {int ans = 1;a = (a % p + p) % p;for (; b; b >>= 1) {if (b &a…
2021/5/5 20:25:59 人评论 次浏览 -
codeforces 715C(点分治+逆元
codeforces 715C(点分治+逆元 题意： 给一个n个点的树，问多少条路径满足边权连成的数%M==0 思路： 考虑点分治按容斥的写法计数，这题细节很多。 首先x1表示从根下来的路径，x2表示上去的路径，维护就很简单了x1∗10(dep2)+x2=0(modm)x1*10^{(dep2)}+x2=0(modm)x1∗10(de…
2021/4/15 10:29:06 人评论 次浏览 -
课后自主练习（dp）1068. 变换种类数 super《编程思维与实践》个人学习笔记
题目思路 ①题目要求是对2、3、5、7可以整除，我们不妨取他们的最小公倍数210来进行状态统计（也可以开一个四维数组【2】【3】【5】【7】来记录状态） ②我们不妨先固定住一个位f(0,0) = 1（比如第零位0（因为没有第0位，就默认是0）先固定好，那么后续有以下情况，+1，-…
2021/4/10 22:11:48 人评论 次浏览
