2015
05-23

# 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

#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
void PRIME(ll Max_Prime){
for(ll i=3;i<=Max_Prime;i+=2)
if(i%prime[j]==0)break;
else if(prime[j]>sqrt((double)i) || j==primenum-1)
{
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;
}