题目链接：http://www.lightoj.com/volume_showproblem.php?problem=1236

题意：给出n，求有多少个数对(i,j)，使得LCM(i,j)=n？

思路：比如24=2^3*3^1：

（1）如果一个数完整地包含了3^1但是没有完整地包含2^3（一个数x完整地包含某个质因数p及其出现的次数t，指x可以被p^t整除），比如3,6,12，那么另一个数必须完整地包含2^3，比如8,24。那么此时有六种组合(3,8),(3,24),(6,8),(6,24),(12,8),(12,24)

（2）若一个数完整地包含2^3但是没有完整地包含3^1,比如8，那么另一个数必须完整地包含3^1,比如3,6,12,24,此时有4个。

（3）若一个数完整地包含了2^3和3^1,比如24，那么另一个数有(3+1)*(1+1)种可能，即1,2,3,4,6,8,12,24。

（4）若一个数既没有完整的包含2^3也没有完整地包含3^1,比如1,2,4，那么另一个数必须为24,此时有3种。

到此为止，你发现除了(24,24)这种组合只在(3)中出现一次，其他情况均出现2次。若上面的总数为t，那么答案为(t+1)/2。

#include 
      
       #include 
       
        #include 
        
         #include 
         
          #define i64 long longusing namespace std;const int MAX=10000005;int prime[MAX/10],cnt;bool tag[MAX];int C,num=0;i64 n;int p[50],q[50],t;void init(){    int i,j;    for(i=2;i
          
           >1;}int main(){    init();    for(scanf("%d",&C);C--;)    {        scanf("%lld",&n);        t=0;        int i;        for(i=1;i<=cnt&&prime[i]<=n;i++) if(n%prime[i]==0)        {            p[t]=prime[i];            q[t]=0;            while(n%prime[i]==0)            {                q[t]++;                n/=prime[i];            }            t++;        }        if(n>prime[i])        {            p[t]=n;            q[t++]=1;        }        printf("Case %d: %lld\n",++num,cal());    }    return 0;}