循环枚举——P1618 三连击（升级版）

来看例题：P1618 三连击（升级版）

初步想法仍然是依次枚举三位数每位上的数字，简单暴力的做法是使用九重循环枚举，每一层枚举1～9九个数字，那么需要枚举\(9^9\)次，在1s内很可能会超时。

其实可以枚举第一个数，第二个数和第三个数可以通过题目中指出的比例计算出来（当然有可能不存在），然后判断是否满足条件（三个数每位上的数字不能重复）。

#include<iostream>
#include<cstring>
using namespace std;
int a[10];
//将三位数n分解并记录每位上数字出现的次数 
void go(int n){
	a[n%10]++;
	a[n/10%10]++;
	a[n/100%10]++; 
}
//检查x,y,z三个三位数每位上的数字是否正好1～９都只出现一次 
bool check(int x,int y,int z){
	memset(a,0,sizeof(a));
	go(x),go(y),go(z);
	for(int i=1;i<=9;i++){
		if(a[i]!=1) return false;
	}
	return true;
} 
int main()
{
	int A,B,C,x,y,z,ans=0;
	cin>>A>>B>>C;
	//枚举第一个数x 
	for(x=123;x<=987;x++){
		//按照整数比例计算另外两个数y和z，如果y、z是小数，不符合 
		if(x*B%A || x*C%A) continue;
		y = x*B/A;
		z = x*C/A;
		if(y>=1000 || z>=1000) continue;
		if(check(x,y,z)) {
			cout<<x<<" "<<y<<" "<<z<<endl;
			ans++;
		}
	}
	if(ans==0) cout<<"No!!!"<<endl;
	return 0;
}