记录编号	142390	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[国家集训队2011]Mario填格子	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	1.590 s
提交时间	2014-12-08 15:53:45	内存使用	0.31 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
using namespace std;
typedef long long LL;
template<typename T> T quickpow(T a,T n,T M){
	a%=M;
	LL ans=1;
	while(n){
		if(n&1) ans=(ans*a)%M;
		a=(a*a)%M;
		n>>=1;
	}
	return ans;
}
bool Rabin_Miller(LL n,LL p){//合数返回0
	if(n==2) return true;
	if(n==1||(n&1)==0) return false;
	LL d=n-1;
	while(!(d&1)) d>>=1;
	LL m=quickpow(p,d,n);
	if(m==1) return true;
	while(d<n){
		if(m==n-1) return true;
		d<<=1;
		m=(m*m)%n;
	}
	return false;
}
bool is_prime(LL n){//素数返回1
	static int rm_primes[]={2,3,5,7,11,13,17,19,23};
	for(int i=0;i<9;i++){
		if(rm_primes[i]==n) return true;
		if(!Rabin_Miller(n,rm_primes[i])) return false;
	}
	return true;
}
LL gcd(LL a,LL b){return !b?a:gcd(b,a%b);}
void Pollard_rho(LL n,vector<LL> &p){//因式分解,存放在p
	if(is_prime(n)){//保证分解出来的都是素数......
		p.push_back(n);
		return;
	}
	int c=3;//随便取个值
	while(true){
		LL x1,x2;
		int i=1,k=2;
		x1=x2=1;
		while(true){
			x1=(x1*x1)%n+c;
			x1%=n;
			LL d=gcd(abs(x1-x2),n);
			if(d!=1&&d!=n){
				Pollard_rho(d,p);
				Pollard_rho(n/d,p);
				return;
			}
			if(x1==x2) break;
			if(++i==k) k<<=1,x2=x1;//启发式
		}
		c++;
	}
}
void get_factor(LL n,vector<pair<LL,int> > &p){
	vector<LL> f;
	Pollard_rho(n,f);
	sort(f.begin(),f.end());
	p.clear();
	for(int i=0;i<f.size();i++){
		if(!i||f[i]!=f[i-1]) p.push_back(make_pair(f[i],1));
		else p.back().second++;
	}
}
vector<pair<LL,int> > P;
bool cmp(pair<LL,int> x,pair<LL,int> y){
	return x.second>y.second;
}
LL ans[3][3];
void assign(LL s[3],LL a,LL b,LL c){
	s[0]=a;s[1]=b;s[2]=c;
}
bool test(LL M,LL N){
	if(N%M) return false;
	if(N/M==1) return false;
	memset(ans,0,sizeof(ans));
	P.clear();
	get_factor(N/M,P);
	sort(P.begin(),P.end(),cmp);
	if(P.size()>=4){
		LL A=P[0].first,B=P[1].first,C=P[2].first,D=P[3].first;
		assign(ans[0],M    ,M*A    ,M*A*C  );
		assign(ans[1],M*B  ,M*A*B  ,M*A*B*C);
		assign(ans[2],M*B*D,M*A*B*D,N      );
		return true;
	}
	if(P.size()>=3&&P[0].second>=2){
		LL A=P[0].first,B=P[1].first,C=P[2].first;
		assign(ans[0],M    ,M*A    ,M*A*A  );
		assign(ans[1],M*B  ,M*A*B  ,M*A*A*B);
		assign(ans[2],M*B*C,M*A*B*C,N      );
		return true;
	}
	if(P.size()>=2&&P[0].second>=2&&P[1].second>=2){
		LL A=P[0].first,B=P[1].first;
		assign(ans[0],M    ,M*A    ,M*A*A  );
		assign(ans[1],M*B  ,M*A*B  ,M*A*A*B);
		assign(ans[2],M*B*B,M*A*B*B,N      );
		return true;
	}
	if(P.size()>=2&&P[0].second>=5){
		LL A=P[0].first,B=P[1].first;
		assign(ans[0],M      ,M*A      ,M*A*A      );
		assign(ans[1],M*B    ,M*A*B    ,M*A*A*A*A*B);
		assign(ans[2],M*A*A*B,M*A*A*A*B,N          );
		return true;
	}
	if(P.size()>=1&&P[0].second>=8){
		LL A=P[0].first;
		assign(ans[0],M    ,M*A*A*A    ,M*A*A*A*A*A*A  );
		assign(ans[1],M*A  ,M*A*A*A*A  ,M*A*A*A*A*A*A*A);
		assign(ans[2],M*A*A,M*A*A*A*A*A,N              );
		return true;
	}
	return false;
}
bool work(void){
	LL M,N;
	if(scanf("%lld%lld",&M,&N)==EOF) return false;
	if(!test(M,N)) printf("Wario_wins!\n");
	else{
		printf("Mario_wins!\n");
		for(int i=0;i<3;i++){
			for(int j=0;j<3;j++)
				printf("%lld ",ans[i][j]);
			printf("\n");
		}
	}
	printf("\n");
	return true;
}
int main(){
	freopen("mario.in","r",stdin);
	freopen("mario.out","w",stdout);
	while(work());
	return 0;
}