首页 > ACM题库 > HDU-杭电 > HDU 4646-Laser Beam-计算几何-[解题报告]HOJ
2015
09-17

HDU 4646-Laser Beam-计算几何-[解题报告]HOJ

Laser Beam

问题描述 :

There is an equilateral triangle consist of 3 mirrors. There is a tiny slit in the corners of the triangle, which can let a laser beam pass through.

Query on a tree VII

We label the 3 slits as A, B and C. There only exists two ways (see the picture above) make a laser beam enter our triangle though C, reflects 11 times in ther triangle, and exit from the triangle though C. The 2 ways are symmetry.

Here is the question for you, our great programmer. How many ways we can make a laser beam enter the triangle though C and exit though C, and the beam reflects n times in the triangle? e.g. there are 80840 ways when n is 1000001.

输入:

The first line contains a number T.(1≤T≤100) Then the following T line each line contains a number n.(1≤n≤107)

输出:

The first line contains a number T.(1≤T≤100) Then the following T line each line contains a number n.(1≤n≤107)

样例输入:

10
2
5
7
11
13
17
19
23
29
31

样例输出:

0
0
2
2
2
0
4
4
2
6

题目是这样的,一个等边三角形,三边都是有镜子组成的。

现在要你从一个点射入一条光线,问你如果要求光线在三角形里面反射n次然后从入点射出来的话,入射的方向可能有多少种?

这。。。。。其实不难。关键是要搞清楚镜子反射的规律。

这样来理解。反射的话相当于在另一面也是一个三角形,这样我们可以把同样的等腰三角形铺满整个二维空间。

这样就会发现规律,如果我们把所有的点都分层,那么发现射到第一层的反射次数为1,第二层为3,第三才层为5,这样下来我们就可以知道如果要反射n次射出的那个对称点应该在那个层数了。

到此我们唯一的问题就是求出每一层有多少个点了。

但是有多少个点就是答案吗?  不是的,如果后面的点被前面的点遮挡了,那么那个点是不算的。

嗯大概就是这样。 基本的解法就是这样的了。。。  只是个人想法。求指教。

 

#include <iostream>
#include <cstdio>
#include <cstring>
#include <map>
#define ll long long
using namespace std;

ll t,n;
map<ll,ll> g;

ll f(ll x)
{
    if (x%2==0) return 2*(x/6+1)-1;
        else return 2*((x-3)/6+1);
}

ll get(ll x)
{
    if (g[x]!=0) return g[x];
    g[x]=f(x);
    for (ll i=2; i*i<=x; i++)
    {
        if (x%i>0) continue;
        g[x]-=get(i);
        if (i*i!=x)
        {
            g[x]-=get(x/i);
        }
    }
    return g[x];
}

int main()
{
    scanf("%I64d",&t);
    while (t--)
    {
        scanf("%I64d",&n);
        if (n%3==0)
        {
            printf("0\n");
            continue;
        }
        if ((n&1)==0)
        {
            printf("0\n");
            continue;
        }
        if (n==1)
        {
            printf("1\n");
            continue;
        }
        if (n==3)
        {
            printf("0\n");
            continue;
        }
        n=(n+3)>>1;
        printf("%I64d\n",get(n));
    }
    return 0;
}

 

参考:http://www.cnblogs.com/Canon-CSU/archive/2013/11/19/3432257.html