关于求 1~n 逆元
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\)。
则 \(a*b^{-1}+x^{-1} \equiv 0 (mod\ p)=>x^{-1}\equiv -(a*b^{-1})\)。令 \(dp[x]={x^{-1}}\),易知 \(a=p/x,b=p\%x\),则 \(dp[x]=-(p/x*dp[p\%x])mod\ p\)。
#include <cstdio> #include <algorithm> #include <cmath> #include <cstring> #include <bitset> #define uint unsigned int #define LL long long using namespace std; const int MAXN = 3e6 + 5; int n, p; LL dp[MAXN]; // 令 p = ax+b, 则 ax+b=0(mod p) // (ax+b)/(bx)=0(mod p) // a*b^(-1)+x^(-1)=0 -> x^(-1)=-(p/x)/(p%x) -> dp[x]=-(p/x)*dp[p%x] int main() { scanf("%d%d", &n, &p); dp[1] = 1; for(int i = 2; i <= n; i ++) dp[i] = -(p / i * dp[p % i]), dp[i] = (dp[i] % p + p) % p; for(int i = 1; i <= n; i ++) printf("%lld\n", dp[i]); return 0; }
- 请注意 \(dp[x]=x^{-1}\),发现这是一个完全积性函数,那么直接跑个埃筛维护即可,若它是质数直接跑费马小定理,否则直接转移,时间复杂度:\(\mathcal {O}(n)+\mathcal {O}(n/ln(n)*log_2(p))\),约等于 \(\mathcal {O}(n)\)。
p.s. \(1-n\) 的质数个数约有 \(n/ln(n)\) 个。
#include <cstdio> #include <algorithm> #include <cmath> #include <cstring> #include <bitset> #define uint unsigned int #define LL long long using namespace std; const int MAXN = 3e6 + 5; int inv[MAXN], prime[MAXN / 10], tot; bitset <MAXN> vis; int n, p; int Quick_Pow(int x, int y) { int ans = 1; for(; y; y >>= 1) { if(y & 1) ans = (LL)ans * x % p; x = (LL)x * x % p; } return ans; } void Prime() { inv[1] = 1; for(int i = 2; i <= n; i ++) { if(!vis[i]) prime[++ tot] = i, inv[i] = Quick_Pow(i, p - 2); for(int j = 1; j <= tot && i * prime[j] <= n; j ++) { vis[i * prime[j]] = 1; inv[i * prime[j]] = (LL)inv[i] * inv[prime[j]] % p; if(i % prime[j] == 0) break; } } } int main() { scanf("%d%d", &n, &p); Prime(); for(int i = 1; i <= n; i ++) printf("%d\n", inv[i]); return 0; }
这篇关于关于求 1~n 逆元的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-09-28微服务架构中API版本控制的实践
- 2024-09-28AI给的和自己写的Python代码,都无法改变输入框的内容,替换也不行
- 2024-09-27Sentinel配置限流资料:新手入门教程
- 2024-09-27Sentinel配置限流资料详解
- 2024-09-27Sentinel限流资料:新手入门教程
- 2024-09-26Sentinel限流资料入门详解
- 2024-09-26Springboot框架资料:初学者入门教程
- 2024-09-26Springboot框架资料详解:新手入门教程
- 2024-09-26Springboot企业级开发资料:新手入门指南
- 2024-09-26SpringBoot企业级开发资料新手指南