P5431 【模板】乘法逆元2

传送门

思路：这题跟模板没什么关系就是卡常数，不懂为什么要这么搞。要用下快读，然后变通分边求和，最后用下费马小定理就行了。

时间复杂度：$O(n+log(mod))$

AC代码：

#include<cstdio>
#include<iostream> 
typedef long long ll;
#define re register//寄存类型变量,加快读取速度
using namespace std;
ll n,p,k,a,x,y=1,k1;//x是分子,y是分母.
char ch;
inline void read(ll &x){ x=0;for(ch=getchar();ch<'0'||ch>'9';ch=getchar());for(;ch>='0'&&ch<='9';ch=getchar())x=(x<<3)+(x<<1)+ch-'0'; 
}
ll ksm(ll x,ll m){//快速幂 ll ans=1;for(;m;x=x*x%p,m>>=1)if(m&1)ans=ans*x%p;return ans;
}
int main(){read(n),read(p),read(k);for(re ll i=1,k1=k%p;i<=n;++i,k1=k1*k%p)read(a),x=(x*a+y*k1)%p,y=y*a%p;//不断通分求和。printf("%lld\n",x*ksm(y,p-2)%p);return  0;
}