首页 > 搜索 > DFS搜索 > HDU 4228-Flooring Tiles-数论-[解题报告]HOJ
2015
05-23

HDU 4228-Flooring Tiles-数论-[解题报告]HOJ

Flooring Tiles

问题描述 :

You want to decorate your floor with square tiles. You like rectangles. With six square flooring tiles, you can form exactly two unique rectangles that use all of the tiles: 1×6, and 2×3 (6×1 is considered the same as 1×6. Likewise, 3×2 is the same as 2×3). You can also form exactly two unique rectangles with four square tiles, using all of the tiles: 1×4, and 2×2.
Given an integer N, what is the smallest number of square tiles needed to be able to make exactly N unique rectangles, and no more, using all of the tiles? If N=2, the answer is 4.

输入:

There will be several test cases in the input. Each test case will consist of a single line containing a single integer N (1 ≤ N ≤ 75), which represents the number of desired rectangles. The input will end with a line with a single 0.

输出:

There will be several test cases in the input. Each test case will consist of a single line containing a single integer N (1 ≤ N ≤ 75), which represents the number of desired rectangles. The input will end with a line with a single 0.

样例输入:

2
16
19
0

样例输出:

4
840
786432

推出了结论,万万没想到最后用搜索。。

还想dp来着。。

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <math.h>
#include <set>
#include <vector>
#include <map>
using namespace std;
#define ll long long
#define N 1000005
ll prime[N],primenum;//有primenum个素数 math.h
void PRIME(ll Max_Prime){
	primenum=0;
	prime[primenum++]=2;
	for(ll i=3;i<=Max_Prime;i+=2)
	for(ll j=0;j<primenum;j++)
		if(i%prime[j]==0)break;
		else if(prime[j]>sqrt((double)i) || j==primenum-1)
		{
			prime[primenum++]=i;
			break;
		}
}
ll n, ans, sum;
void dfs(ll a,ll s, ll t, ll l){
	if(s>n<<1)return ;
	if(s==2*n || s==2*n-1){
		ans = min(ans, a);
		return ;
	}
	if(t>20)return;
	for(ll i = 1; i <= l; i++) {
	a *= prime[t];
	dfs(a,s*(i+1), t+1,i);
	}
}
int main(){
	ll i,j,u,v;
	PRIME(100);
	while(cin>>n, n) {
	ans = 1e18;
	dfs(1,1,0,60);
	cout<<ans<<endl;
	}	
	return 0;
}

版权声明:本文为博主原创文章,未经博主允许不得转载。

参考:http://blog.csdn.net/qq574857122/article/details/37116459