首页 > 其他分享 >P5431 【模板】乘法逆元 2

P5431 【模板】乘法逆元 2

时间:2022-10-04 16:47:35浏览次数:53  
标签:ch int ll sv read P5431 逆元 ans 模板

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 const int N = 5e6 + 10;
 5 ll fac[N], sv[N], inv[N], a[N];
 6 ll n, p, k;
 7 void read(ll &x) {
 8     x = 0; int f = 1; char ch = getchar();
 9     while (ch < '0' || ch >'9') {if (ch == '-') f = -1; ch = getchar();}
10     while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
11     x *= f;
12 }
13 ll quickpow(ll x, ll y) {
14     ll ans = 1;
15     while (y) {
16         if (y & 1) ans = ans * x % p;
17         x = x * x % p;
18         y >>= 1;
19     }
20     return ans % p;
21 }
22 signed main() {
23     read(n), read(p), read(k);
24     fac[0] = 1;
25     for (int i = 1; i <= n; i ++) {
26         read(a[i]);
27         fac[i] = fac[i - 1] * a[i] % p;
28     } 
29     sv[n] = quickpow(fac[n], p - 2);
30     for (int i = n; i >= 1; i --) sv[i - 1] = sv[i] * a[i] % p;
31     ll tmp = 1, ans = 0;
32     for (int i = 1; i <= n; i ++) {
33         tmp = (tmp * k) % p;
34         ans = (ans + ((sv[i] * fac[i - 1] % p)) * tmp) % p;
35     }
36     printf("%lld\n", ans);
37     return 0;
38 }

 

标签:ch,int,ll,sv,read,P5431,逆元,ans,模板
From: https://www.cnblogs.com/yhxnoerror/p/16753991.html

相关文章

  • ToroiseGit/GitBash 设置提交信息模板设置
    导航:一、背景二、ToroiseGit实施方案:三、GitBash实施方案 一、背景:当使用git提交代码时,每次的提交信息固定,却又比较长不好记的时,还需要将模板的地址保存下来,如果能设置......
  • 元模板 笔记
    对类型编写,由于c++不存在if(type==xxx){}这种语法。类型计算可以使用:1,重载。2,虚函数。继承。3,c语言中利用Union查看代码structVariant{union{......
  • Modular int模板
    防止一切因为忘记模数而导致爆0的事情发生!template<intmod>structmint{unsignedint_v;mint():_v(0){}template<classT>mint(Tv){......
  • 求逆元,欧拉函数,中国剩余定理
    求a/b的mod等价于a*b逆的mod求1到n的逆元可以用线性法1intins[N];2intmain(){3intn,p;4cin>>n>>p;5for(inti=2;i<=n;++i){6......
  • Latex 如何写算法?推荐模板
    之前我已经在​​这篇文章​​总结了现有的算法包的区别。如果有选择苦难症的朋友可以考虑无脑使用以下模板来写算法。\usepackage[noend]{algpseudocode}#noend表示算法......
  • 驱动开发:应用DeviceIoContro开发模板
    内核中执行代码后需要将结果动态显示给应用层的用户,DeviceIoControl是直接发送控制代码到指定的设备驱动程序,使相应的移动设备以执行相应的操作的函数,如下代码是一个经典的......
  • 驱动开发:应用DeviceIoContro开发模板
    内核中执行代码后需要将结果动态显示给应用层的用户,DeviceIoControl是直接发送控制代码到指定的设备驱动程序,使相应的移动设备以执行相应的操作的函数,如下代码是一个经典......
  • 抽象类及模板设计模式
    1基本介绍当父类的某些方法,需要声明,但是又不确定如何实现时,可以将其声明为抽象方法,那么这个类就是抽象类当父类的一些方法不能确定时,可以用abstract关键字来修饰该方......
  • springboot整合thymeleaf模板引擎和bootstrap实现增删改查和文件上传
     一、参照第八天任务中的栏目表,使用thymeleaf做为前端展现,完成CRUD及分页操作二、使用springboot+mybatis-plus+redis完成用户登录系统,数据库表users字段名称......
  • 深度学习Vue源码-模板编译原理
    前言此篇主要手写Vue2.0源码-模板编译原理上一篇咱们主要介绍了Vue数据的响应式原理对于中高级前端来说响应式原理基本是面试Vue必考的源码基础类如果不是很清......