2015
05-23

# HDU 4304-Let’s Hit Our Head!-数论-[解题报告]HOJ

Kingdom LHOH is celebrating its annual carnival again!This time another crazy game is now on show.N*N piles of brick here lying on the ground in a straight line, and N brave fellows have attended.
First they should each choose a distinct piles brick to stand behind, forming a line parrelling to the brick, and facing the same side, watching at his piles of brick.
Then their captain can yelled out 3 commands, described below:
A "LEFT!" Every one should move so that he is behind the left piles of the original one.
B "RIGHT!" Every one should move so that he is behind the right piles of the original one.
C "HIT!" Every one should break all the piles of brick before him with only his head slamming them.

A little constraints are showed below:
In every step, when command A or B have been yelled out, no one should move outside, that is, for everyone after his moving, brick(even breaked up) is there before him,and when command C is to be yelled out, intact piles of brick must be there before every one, so that he cannot slamming brick that it already breaked up, and only that is fair to everyone.
Not until all piles of brick have been successfully breaked up with the brave fellows’ heads, this game is successfully finished.
Now the question is,the crazy captain wants to know how many initial options are there,satisfying for each initial option he always chooses the first piles, other members choose their own distinct ones,and the game can be finished successfully at the same time?
We assume the other members except the captain cannot be told out.

First there’s an integer T(T<=15000) indicating the scenary numbers.
Then there’s T lines represented for the scenaries, with an integer N(1<=N<=10^12) in each line.

First there’s an integer T(T<=15000) indicating the scenary numbers.
Then there’s T lines represented for the scenaries, with an integer N(1<=N<=10^12) in each line.

10
1
2
3
4
8
16
6469693228
6469693229
6469693230
1024

1
2
2
6
20
70
84
14
8787513806478134
184756

1. 人全部右移（石头不动）。

2. 人全部左移。

3. 将自己面前的石头全部用脑袋砸碎。

1.左右移的时候不能移出去，就是每人面前都得有一堆石头，无论是坏的还是好的。

2.砸的时候只能砸未砸过的石头。

A6B6 B6A6
A2B6A3 A3B6A2 B2A6B3 B3A6B2
A2B2A3B3 A2B3A3B2 A3B3A2B2 A3B2A2B3
B2A2B3A3 B2A3B3A2 B3A3B2A2 B3A2B2A3

A8B8 B8A8
A2B8A4 A4B8A2 B2A8B4 B4A8B2
A2B2A4B4 A2B4A4B2 A4B2A2B4 A4B4A2B2
B2A2B4A4 B2A4B4A2 B4A2B2A4 B4A4B2A2
A2B2A2B4A2 A2B4A2B2A2 B2A2B2A4B2 B2A4B2A2B2
A2B2A2B2A2B2 B2A2B2A2B2A2

#include <cstdio>
#include <cstring>

int coef[20],delt[20],inx[20],base[20];
int mark[1000010],pri[1000010],priN;
__int64 dp[2000][20];

void init()
{
int i,j;
for(i=2; i<=1000000; i++) mark[i]=i;
for(i=2; i<=1000000; i++)
{
if(mark[i]==i) pri[priN++]=i;
for(j=0; j<priN&&i*pri[j]<=1000000; j++)
{
mark[i*pri[j]]=pri[j];
if(i%pri[j]==0) break;
}
}
}

void deal()
{
__int64 u,ans,num,t,tmpv;
int cnt,i,j,k,l,prod,tot,amn,m;
scanf("%I64d", &u);
for(cnt=0,num=u; num-1;)
{
if(num>1000000)
{
t=num;
for(j=0; j<priN; j++)
{
if(num%pri[j]==0)
{
t=pri[j];
break;
}
}
}
else t=mark[num];
inx[cnt]=0;
while(num%t==0) num/=t,inx[cnt]++;
cnt++;
}
for(tot=0,prod=1,i=cnt-1; i>=0; i--)
{
tot+=inx[i],base[i]=prod,prod*=(inx[i]+1);
}
for(i=0; i<=tot; i++) for(j=0; j<prod; j++) dp[j][i]=0;
dp[0][0]=1;
for(i=1; i<prod; i++)
{
for(j=0; j<cnt; j++) delt[j]=i/base[j]%(inx[j]+1);
for(j=prod-1; j>=0; j--)
{
amn=0x3fffffff;
for(k=0; k<cnt; k++)
{
coef[k]=j/base[k]%(inx[k]+1);
if(delt[k])
{
tmpv=(inx[k]-coef[k])/delt[k];
if(tmpv<amn) amn=tmpv;
}
}
for(l=1; l<=amn; l++)
{
for(k=0; k+l<=tot; k++)
{
tmpv=dp[j][k];
for(m=1; m<=l; m++) tmpv*=m+k,tmpv/=m;
dp[j+i*l][k+l]+=tmpv;
}
}
}
}
for(ans=dp[prod-1][tot]*dp[prod-1][tot],i=0; i<tot; i++)
{
ans+=(dp[prod-1][i]+dp[prod-1][i+1])*(dp[prod-1][i]+dp[prod-1][i+1]);
}
printf("%I64d\n", ans);
}

int main()
{
init();
int t;
scanf("%d", &t);
while(t--) deal();
return 0;
}