2015
09-17

# 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.

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

#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;
}