洛谷P3811 【模板】乘法逆元（递推）

2019-04-13 13:39发布

站内文章 / 模拟电子
17640 0 1341

【模板】乘法逆元

题目背景 这是一道模板题 题目描述 给定n,p求1~n中所有整数在模p意义下的乘法逆元。 输入输出格式 输入格式：
一行n,p 输出格式：
n行,第i行表示i在模p意义下的逆元。 输入输出样例 输入样例#1：
10 13
输出样例#1：
1
7
9
10
8
11
2
5
3
4 分析：有一个递推式，不会证，ny[i]=(p-p/i)*ny[p%i] 代码 #include #define N 3000005 #define ll long long using namespace std; ll a[N],p; int n; int main() { scanf("%d%lld",&n,&p); a[1]=1; printf("1 "); for (int i=2;i<=n;i++) { a[i]=(p-p/i)*a[p%i]%p; printf("%lld ",a[i]); } }

热门文章