题目描述

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

由于输出太多不好,所以将会给定常数 k,你要输出的答案为:

i=1nkiai\sum\limits_{i=1}^n\frac{k^i}{a_i}

答案对 p 取模。

输入格式

第一行三个正整数 n,p,k,意义如题目描述。
第二行 n 个正整数 aia_i,是你要求逆元的数。

输出格式

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

输入输出样例

输入 #1

6 233 42
1 4 2 8 5 7

输出 #1

91

说明/提示

对于 30% 的数据,1n1051\le n \le 10^5

对于 100% 数据,1n5×1062k<p1091ai<p1\le n \le 5\times 10^6,2\le k < p \le 10^9,1\le a_i < p,保证 p 为质数。

题目分析

将题目要求的式子展开

k1a1+k2a2++knan\frac{k^1}{a_1}+\frac{k^2}{a_2}+\cdots +\frac{k^n}{a_n}

我们进行通分,可得

k1a2an+k2a1a3an++kna1an1a1a2an(modp)\frac{k^1a_2\cdots a^n+k^2a_1a_3\dots a_n+\cdots+k^na_1\cdots a_{n-1}}{a_1a_2\dots a_n}(\mod p)

同余连续性对于除法来说是不成立的,可以利用逆元,将除法转化为乘法。

a/bax(modm)a/b\equiv ax (\mod m),x为b的逆元。

计算a/ba/b这样的除法算式,可以先把a,b各自对模数p取模,再计算a×b1(modm)a\times b^{-1}(\mod m)作为最终的结果。

ans=(k1a2an++kna1an1)×(a1a2an)1(modp)ans=(k^1a_2\cdots a^n+\cdots+k^na_1\cdots a_{n-1})\times({a_1a_2\dots a_n})^{-1}(\mod p)

利用费马小定理求逆元:inv=ap2%pinv=a^{p-2}\%p

代码实现

#include <iostream>
#include <cstdio>
using namespace std;
const int N=5e6+5;
typedef long long ll;
int n,p,k;
ll mypow(ll x,ll n,int M){//快速幂
	if(n==0) return 1%M;
	ll tmp=mypow(x,n/2,M)%M;
	if(n&1) return tmp*tmp%M*x%M;
	else return tmp*tmp%M;
}
int main(){
	ll a,fz=0,fm=1;
	scanf("%d%d%d",&n,&p,&k);
	ll cf=k%p;
	for(int i=1;i<=n;i++){
		scanf("%lld",&a);
		//当前分子: 前面的分子 * 新分母 + 之前分母*当前分子 
		fz=(fz*a%p+fm*cf%p)%p;
		cf=cf*k%p;
		fm=fm*a%p;
	}
	printf("%lld",fz*mypow(fm,p-2,p)%p);
	return 0;
}

Q.E.D.


( ノ^ω^)ノ゚ 稻 花 香 里 说 丰 年 , 听 取 WA 声 一 片 。(╥╯^╰╥)