本文共 1256 字，大约阅读时间需要 4 分钟。

题目

给定 n 个正整数 $a_i$，求它们在模 $p$ 意义下的乘法逆元。

由于输出太多不好，所以将会给定常数 $k$，你要输出的答案为: $\sum _{i=1}^n\frac{k^i}{a_i}$ 当然要对 p 取模。

输入格式

第一行三个正整数 n,p,k 意义如题目描述。

第二行 n 个正整数 a_i ，是你要求逆元的数。

输出格式

输出一行一个整数，表示答案。

输入输出样例

输入

6 233 421 4 2 8 5 7

输出

91

说明/提示

对于 30 分的数据：

$1\le n\le 10^5$ 对于全部数据： $1\le n\le 5\times 10^6$

$2\le k<p\le 10^9$

$1\le a_i<p$ 保证p为质数。

$\text{请注意常数优化}$

思路

主流的做法是什么前缀积、后缀积，还有一堆常数优化。

但在一篇上看到更简单的方法： 首先边读入边通分， 我们由费马小定理：$a^{p-1}\equiv 1(modp)$，结合乘法逆元：$ax\equiv 1(modp)$， 可得： $x=a^{p-2}$，再用快速幂求出即可

代码

#include
   
    #include
    
     #define ll unsigned long longusing namespace std;ll n,p,k,kt,a,at,b=1;ll read(){
   	char ch=getchar();	ll x=0;	while(ch<'0'||ch>'9') ch=getchar();	while(ch>='0'&&ch<='9')	{
   		x=(x<<3)+(x<<1)+ch-48;		ch=getchar(); 	}	return x;}ll fpow(ll a,ll b) //快速幂{
   	ll ans=1;	while(b)	{
   		if(b&1) ans=(ans*a)%p;		a=a*a%p;		b>>=1;	}	return ans;}int main()   {
   		n=read();	p=read();	k=read();	kt=k%p; 	for(ll i=1;i<=n;i++)	{
   		at=read();		a=(b*kt%p+a*at%p)%p;		b=b*at%p;		kt=kt*k%p;	}	printf("%lld",a*fpow(b,p-2)%p);}
    
   

转载地址：http://thpwb.baihongyu.com/