持续更新
A - 乘法逆元
求 \(1∼n\) 中的所有数在模 \(p\) 意义下的乘法逆元
1.快速幂
根据欧拉定理,若\(a\)和\(p\)互质,则\(a^{\varphi(p)}\equiv1\;(mod\;p)\),当\(p\)是质数,则满足:
\(p\) 为质数, \(a\) 为正整数, \(a\) 和 \(p\) 互质, 则\(a^{p-1} \equiv 1\;(mod\;p)\).
根据费马小定理: \(a \times a^{p-2} \equiv 1\;(mod \; p)\), \(a^{p-2}\;(mod\;p)\)即为\(a\)的逆元, 利用快速幂求解即可.
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int n, p;
int pow_mod(int a, int b, int p)
{
int res = 1;
while(b)
{
if(b & 1) res = (LL)res * a % p;
a = (LL)a * a % p;
b >>= 1;
}
return res;
}
int main()
{
scanf("%d%d", &n, &p);
for(int i = 1; i <= n; ++ i)
printf("%d\n", pow_mod(i, p - 2, p));
return 0;
}
2.扩展欧几里得
当\(a\)和\(p\)互质,但\(p\)不是质数时,解线性同余方程\(a*x\equiv1\;(mod\;p)\):
转化为:\(a*x+p*y\equiv1\),因为\(a\)和\(p\)互质,所以一定有解,用exgcd求解即可
exgcd解出的逆元有可能是负数,转化成\(mod\;p\)意义下的正数即可
#include <bits/stdc++.h>
using namespace std;
int exgcd(int a, int b, int &x, int &y)
{
if(!b)
{
x = 1, y = 0;
return a;
}
int d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
int main()
{
int n, p;
scanf("%d%d", &n, &p);
for(int i = 1; i <= n; ++ i)
{
int x, y;
exgcd(i, p, x, y);
x = (x % p + p) % p;
printf("%d\n", x);
}
return 0;
}
3.线性递推
设\(p = k * i + r\), \(k\)是\(\dfrac{p}{i}\)的商,\(r\)是余数
\(k*i+r\equiv0\;(mod\;p)\), 两边同时乘上\(i^{-1}\)和\(r^{-1}\)
\(k * r^{-1} + i^{-1} \equiv 0\;(mod\;p)\)
\(i^{-1} \equiv -k * r^{-1}\;(mod\;p)\)
\(i^{-1} \equiv -\left\lfloor\dfrac{p}{i}\right\rfloor * (p\;mod\;i)^{-1}\;(mod\;p)\)
且已知\(1^{-1}\equiv1\;(mod\;p)\),则可以线性递推
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 3e6 + 20;
int inv[N];
int main()
{
int n, p;
scanf("%d%d", &n, &p);
inv[1] = 1; puts("1");
for(int i = 2; i <= n; ++ i)
{
inv[i] = (LL)(p - p / i) * inv[p % i] % p;
printf("%d\n", inv[i]);
}
return 0;
}
B - 除数函数求和 1
\(\sigma_k(n) = \sum_{d|n}d^k\), 求\(\sum_{i=1}^n\sigma_k(i)\)的值对\(10^9 + 7\)取模的结果.