2015
05-23

# Laser Tag

A Laser Tag environment is set up with a number of upright, rectangular, double-sided mirrors, all reaching high over head. These mirrors can reflect your laser beam, allowing you multiple ways to shoot your opponents. Unfortunately, they can also reflect your laser beam in such a way that it hits you by mistake. Your job is to calculate the angles that result in shooting yourself (so that you can avoid them).
The mirrors are not perfectly reflective, so we only need to worry about shots with at most 7 reflections. Below are several possible setups. In the figures the views are looking down from above. The mirrors are shown as black segments. All the paths that lead back to the firing point are shown in gray. Take the point of firing as the center of a Cartesian coordinate system, with postive x to the right and positive y up the page. The coordinates of the origin and the ends of the mirrors are shown. For simplicity assume the mirrors have negligible thickness. Each path is labeled with the initial firing angle, measured in degrees counterclockwise from the postive x axis and rounded to the nearest degree, 0 through 359.


The input contains one or more data sets. Each data starts with a line containing the number of mirrors, n, 1 ≤ n ≤ 7. The next n lines each contain the (x, y) coordinates of the ends of one mirror, so there is a sequence of 4 numbers for each mirror, x1 y1 x2 y2. All coordinates are integers with magnitude less than 1000. No mirrors intersect or touch. No mirror passes through the origin.
After the last dataset is a line containing only 0.

The input contains one or more data sets. Each data starts with a line containing the number of mirrors, n, 1 ≤ n ≤ 7. The next n lines each contain the (x, y) coordinates of the ends of one mirror, so there is a sequence of 4 numbers for each mirror, x1 y1 x2 y2. All coordinates are integers with magnitude less than 1000. No mirrors intersect or touch. No mirror passes through the origin.
After the last dataset is a line containing only 0.

2
2 1 -1 4
-2 4 -2 -1
4
3 10 13 10
-13 17 -7 23
33 17 27 23
10 -10 20 -10
3
3 10 13 10
-13 17 -7 23
33 17 27 23
0

45 67 90 135 157 180
29 61 63 117
no danger

由于每个素数因子的个数有限（不超过20个）直接打表（dfs）计算出所有的最小公倍数；

然后DP更行最小公倍数即可；

这个题目要做一些优化（囧，TLE一次）：

首先，二分查找，找到要更新的公倍数对应的位置；再次，就是把结果打表，然后每次求和即可。

原来是二分的上界 写成了36863.。。囧少写了一个WA半天。（2011-09-19 01:02）。

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

long long Lcm[ 42 ];
long long Pri[ 12 ] = {2,3,5,7,11,13,17,19,23,29,31,37};
long long Num[ 12 ] = {5,3,2,1,1,1,1,1,1,1,1,1};
long long Sav[ 36880 ];
long long Count = 0;
long long F[ 42 ][ 36880 ];

long long gcd( long long a, long long b )
{
return a%b?gcd( b, a%b ):b;
}

long long lcm( long long a, long long b )
{
return a/gcd( a, b )*b;
}

void dfs( int s, long long v )
{
if ( s == 12 ) Sav[ Count ++ ] = v;
else
for ( int i = 0 ; i <= Num[ s ] ; ++ i ) {
long long save = 1LL;
for ( int j = 0 ; j < i ; ++ j )
save *= Pri[ s ];
dfs( s+1, v*save );
}
}

int cmp( const void* a, const void* b )
{
long long *p = (long long *)a;
long long *q = (long long *)b;
if ( *p < *q ) return -1;
else return 1;
}

int search( long long V )
{
int m,l = 1,h = 36864;
while ( l < h ) {
m = (l+h+1)>>1;
if ( Sav[ m ] > V )
h = m-1;
else l = m;
}
return h;
}

int main()
{
Lcm[ 1 ] = 1;
for ( int i = 2 ; i <= 40 ; ++ i )
Lcm[ i ] = lcm( Lcm[ i-1 ], i );
Count = 0LL;
dfs( 0, 1LL );
qsort( Sav, Count+1, sizeof( long long ), cmp );

for ( int i = 1 ; i <= 40 ; ++ i )
for ( int j = 0 ; j <= Count ; ++ j )
F[ i ][ j ] = 0LL;

for ( int i = 1 ; i <= 40 ; ++ i ) {
for ( int j = 1 ; j <= Count ; ++ j )
F[ i ][ j ] = F[ i-1 ][ j ];
for ( int j = 1 ; j <= Count ; ++ j )
F[ i ][ search( lcm( Sav[ j ], i ) ) ] += F[ i-1 ][ j ];
F[ i ][ i ] += 1LL;
}

long long T,N,M;
while ( ~scanf("%I64d",&T) )
for ( int t = 1 ; t <= T ; ++ t ) {
scanf("%I64d%I64d",&N,&M);
int V = search( Lcm[ N ] );

long long sum = 0LL;
for ( int i = 1 ; i <= V ; ++ i )
if ( Sav[ i ] >= M )
sum += F[ N ][ i ];

printf("Case #%d: %I64d\n",t,sum);
}
return 0;
}