C++ 解法, 执行用时: 26ms, 内存消耗: 416K, 提交时间: 2022-06-25 13:01:03

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define N 105
int cnt,n; ll P,m,a[N];
struct node{
	ll p,sum,num,val;
}c[N];
void fzt(ll x){
	ll i;
	for (i=2; i*i<=x; i++)
	if (!(x%i))
	for(c[++cnt].p=i,c[cnt].sum=1;!(x%i);x/=i)
	{
		c[cnt].num++;
		c[cnt].sum*=i;
	}
	if (x!=1)
	{
		c[++cnt].p=x;
		c[cnt].num=1;
		c[cnt].sum=x;
	}
}
ll ksm(ll x,ll y,ll mod)
{
	ll sum=1,base=x;
	while (y)
	{
		if (y&1)
		sum=sum*base%mod;
		base=base*base%mod;
		y>>=1;
	}
	return sum;
}
void exgcd(ll u,ll v,ll &x,ll &y){
	if (!v){
		x=1;
		y=0;
		return;
	}
	else{
		exgcd(v,u%v,y,x);
		y-=x*(u/v);
	}
}
ll getivs(ll x,ll p){
	ll t1,t2; exgcd(x,p,t1,t2);
	return (t1%p+p)%p;
}
ll crt(){
	int i; ll sum=0;
	for (i=1; i<=cnt; i++){
		ll t1,t2;
		exgcd(c[i].sum,P/c[i].sum,t1,t2);
		t2=(t2%P+P)%P;
		sum=(sum+P/c[i].sum*t2*c[i].val)%P;
	}
	return (sum%P+P)%P;
}
void solve(int k,ll x,ll &t1,ll &t2){
	ll i,u,v; t1=1; t2=x/c[k].p;
	for (i=1; i<c[k].sum; i++)
	if(i%c[k].p)
	t1=t1*i%c[k].sum;
	t1=ksm(t1,x/c[k].sum,c[k].sum);
	for(i=x-x%c[k].sum+1; i<=x; i++)
	if(i%c[k].p)
	t1=t1*i%c[k].sum;
	if (t2){
		solve(k,t2,u,v);
		t1=t1*u%c[k].sum;
		t2+=v;
	}
}
int main(){
	scanf("%lld%lld%d",&P,&m,&n);
	int i,j,sum=0;
	for (i=1; i<=n; i++)
	{
		scanf("%lld",&a[i]);
		sum+=a[i];
	}
	if (sum>m)
	{
		cout<<"Impossible"<<endl;
		return 0;
	}
	if (sum<m) a[++n]=m-sum;
	fzt(P);
	for (i=1; i<=cnt; i++)
	{
		ll t1,t2; solve(i,m,t1,t2);
		for (j=1; j<=n; j++)
		{
			ll u,v;
			solve(i,a[j],u,v);
			t2-=v;
			t1=t1*getivs(u,c[i].sum)%c[i].sum;
		}
		c[i].val=t1*ksm(c[i].p,t2,c[i].sum)%c[i].sum;
	}
	printf("%lld\n",crt());
	return 0;
}