[UVA] 12137 - Puzzles of Triangles
Puzzles with geometric shapes are very interesting and is said to have great impact in developing geometric insight of a child. ACM (Actual Challenge Makers) is planning to bring out one such puzzle. The specialty of this puzzle is that all the pieces of this puzzle have the shape of right-angled triangles. All these right angled pieces make the target rectangular shape and it is shown in figure 2.
It may be a bit difficult to construct or even reconstruct a puzzle which is only composed of pieces with the shape of a right-angled triangle. However if the actual rectangular puzzle is divided into several square sub-regions, and then those sub-regions are divided into four right-angled pieces then such puzzles are easy to make and solve.
|
|
|
|
Figure 1: A cut to make four right angled triangle shaped pieces. |
Figure 2: A conventional puzzle of triangles. |
Whether a rectangle can be divided into small pieces of squares can itself be an interesting task to solve. But that is not the problem you have to solve here. Your job is to decide whether a square shaped sheet can be divided into four right-angled triangles as shown in figure 1. The machine that is used to cut the pieces can only deal with integers. So the length of the square shaped sheets is always expressed in integer units and also cutter can only cut in a straight line from one integer coordinate to another. The cutting must start on one of the corners of the square shaped sheet, continue cutting in a triangular path (Like AEF showed in Figure 1) and again finish at the corner it started. And if four corners of the square sheet are lattice points (0,0), (N,0), (N,N) and (0,N), where N is the length of sides of the square shaped sheet then point E and F should also be lattice points. So given a sheet, you have to determine whether such cuts are possible, and if it is possible then in how many ways.
Input
The input file contains at most 800 lines of inputs.
Each line contains an integer N (0<N<1014), which means that we have to cut an (NxN) sheet.
Input is terminated by a line containing a single zero. This zero should not be processed.
Output
For each line of input produce one line of output. This line contains the serial of output followed by a string or an integer. If it is not possible to cut the (NxN) sheet in the prescribed way, then print a line �Impossible�, otherwise print an integer W. Here W denotes the number of ways such a cut is possible. Look at the output for sample input for details
Sample Input��������������������������� Output for Sample Input
|
10 20 100 32 0 |
Case 1: Impossible Case 2: 8 Case 3: 72 Case 4: 24
|
Problem setter: Shahriar Manzoor, Special Thanks: Derek Kisman
題目描述：
從正方形的一角出發，如附圖會產生四個直角三角形，並且所有座標都是整數。
問總共有幾種方法可以產生四個直角三角形。
題目解法：
很明顯地會發現左右對稱，而且四個角又相同，因為考慮一種最後 * 8。
再來會發現產生直角的地方，左右剛好是相似形。
Figure 1:
ABE ~= CEF
BE = a, CE = N-a
N/a = (N-a)/CF, CF = x = (N-a)*a/N = a - (a*a)/N
a < N, a*a >= N, a*a%N = 0
因此目標要找到有多少 a 符合上述條件。
先找到一個最小符合的 a，然後找到 a * k < N 的最大 k 值就是個數。
#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;
#define maxL (10000000>>5)+1
#define GET(x) (mark[(x)>>5]>>((x)&31)&1)
#define SET(x) (mark[(x)>>5] |= 1<<((x)&31))
int mark[maxL];
int p[670000], pt = 0;
void sieve() {
register int i, j, k;
SET(1);
int n = 10000000;
for(i = 2; i <= n; i++) {
if(!GET(i)) {
p[pt++] = i;
for(k = n/i, j = i*k; k >= i; k--, j -= i)
SET(j);
}
}
}
/*
Figure 1:
ABE ~= CEF
BE = a, CE = N-a
N/a = (N-a)/CF, CF = x = (N-a)*a/N = a - (a*a)/N
a < N, a*a >= N, a*a%N = 0
*/
int main() {
sieve();
long long n;
int cases = 0;
int i, j, k;
while(scanf("%lld", &n) == 1 && n) {
long long mn_a = 1, on = n;
for(i = 0; i < pt && p[i]*p[i] <= n; i++) {
if(n%p[i] == 0) {
int cnt = 0;
while(n%p[i] == 0)
n /= p[i], cnt++;
cnt = (cnt+1)/2;
for(j = 0; j < cnt; j++)
mn_a *= p[i];
}
}
if(n != 1) mn_a *= n;
long long ret = on/mn_a - 1;
// k = on/mn_a => a = mn_a * k, k = 1, 2, 3, ..., but not a = N
printf("Case %d: ", ++cases);
if(ret == 0)
puts("Impossible");
else
printf("%lld\n", ret*8);
}
return 0;
}