首页 > ACM题库 > HDU-杭电 > HDU 4208-Laser Tag-数论-[解题报告]HOJ
2015
05-23

HDU 4208-Laser Tag-数论-[解题报告]HOJ

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.
Grade School Multiplication
    

Grade School Multiplication

输入:

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

题目:从1~n去若干个数字,使得他们的最小公倍数不小于M的有多少种。

分析:dp,数论,搜索。其实就是一个背包类似物。(貌似离散化dp写起来很简洁)

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

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

             这个题目要做一些优化(囧,TLE一次):

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

说明:在比赛进行了2:30小时之后,我们终于A掉了第一道题,随即我终于找到了这个题的bug并将它A了;

             原来是二分的上界 写成了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;
}

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

参考:http://blog.csdn.net/mobius_strip/article/details/39429937