UVA725

解題心得

一開始看到這題完全沒有頭緒，看了CPE提供的解說影片才有想法。

首先，用列舉的方式窮舉所有可能，如果該數字組合符合等式，再檢查數字是否重複。判斷等式成立與否也未必要用除的，用分母乘以N得到分子，這樣能縮小窮舉範圍。

思考到這裡，剩下的就是枚舉所有可能的分母，只要乘以N必定能讓等式成立，而分母的窮舉範圍其實可以進一步縮減到01234~98765。

太久沒解題，最後還卡在換行上XD

程式碼

#include <iostream>
using namespace std;

bool isValid(int a, int b)
{
	if(a>99999 || b>99999) return false;
	
	int count[10] = {0};
	if(a<10000) count[0]++;
	if(b<10000) count[0]++;
	while(a>0)
	{
		count[a%10]++;
		a/=10;
	}
	while(b>0)
	{
		count[b%10]++;
		b/=10;
	}
	for(int i=0;i<10;i++)
	{
		if(count[i]!=1)
			return false;
	}
	return true;
}

int main()
{
	int n;
	bool isFirst=true;
	
	while(cin>>n)
	{
		if(n==0) break;
		
		bool hasAns=false;
		
		if(isFirst) isFirst=false;
		else cout<<endl;
		
		for(int i=1234;i<=98765;i++)
		{
			int j = i * n;
			if(isValid(i, j))
			{
				hasAns=true;
				if(j<10000) cout<<"0"<<j<<" / ";
				else cout<<j<<" / ";
				if(i<10000) cout<<"0"<<i<<" = "<<n<<endl;
				else cout<<i<<" = "<<n<<endl;
			}
		}
		if(!hasAns) cout<<"There are no solutions for "<<n<<"."<<endl;
		
		
	}
	return 0;
}