Magic fast power

  Ideas ;
Pure simulation is definitely a gift , There are many people who are looking for rules , Find the circular section and then pass .

I saw a show on the Internet and turned my thoughts ： Treat an infection process as a multiplication operation , The operation object is the tag array , I've been through so much k operations , That is, take k Time , This is a fast power of deformation

Then just click on the fast power

The overall complexity is about m^2*log(k),4e7 The level of , Theoretically, it can pass

but, Time is still dead （ Maybe the constant is a little big ）, You have to add all the miscellaneous optimizations ： Fast reading ,register,inline...

Optimized to the extreme , To live through ...（ Personal experience ）

Although but , This idea is really the first time I have seen , Very good

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lowbit(x) x&(-x)
const int N=1500;
ll k;
int m,n;
inline ll read() {
    register char ch;
    while(!isdigit(ch=getchar()));
    register ll x=ch^'0';
    while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
    return x;
}
bool mas[N],tp[N],ans[N];
inline void mul(bool a[],bool b[])
{
	memset(tp,0,sizeof tp);
	for(register int i=0;i<m;++i)
	{
		for(register int j=0;j<m;++j)
		{
			tp[i*j%m]|=a[i]&&b[j];
		}
	}
	std::copy(&tp[0],&tp[m],a);
}
int main()
{//ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	k=read();m=read();n=read();
	for(register int i=1;i<=n;++i)
	{
		//a=read();
		mas[read()]=1;
	}
	ans[1]=1;
	while(k)
	{
		if(k&1) mul(ans,mas);
		mul(mas,mas);
		k>>=1;
	}
	for(register int i=0;i<m;++i) if(ans[i]) printf("%d ",i);
	return 0; 
 }