题意：定义K-维数M：如果M的因数个数为K,则M为K-维数。题目的要求是求第N个K-维数。N<10000,Kmax<=100,Kmax是K的最大质因数。如果K是一个kk-维数，则kk<=3。

分析：
如果M = x1^p1 * x2^p2 * ... * xn^pn (x1,x2...xn均为质数）,则 K = (p1＋1)*(p2＋1)*...*(pn＋1).
 
这道题重要的条件是：如果K是一个kk-维数，则kk<=3。根据这个条件可以确定K的范围。kk的取值只有三种1，2，3。如果kk=1,则K=1；如果kk=2,K=p（p为质数）；如果kk=3,K=p^2(p为质数)。
 
分情况讨论，如果K = 1,则原数M只可能为1，因为只有1的因数个数为1。如果K = p(p为质数),则原数M = x^(p-1)（x也为质数）,找到第n个数只需遍历一下质数表就可以了。如果K=p^2(p为质数)，则原数M = x1^(p-1)*x2^(p-1) = (x1*x2)^(p-1) (x1,x2均为质数且不等),或者 M = x1^(K-1) (x1为质数）。这种情况下找到第n个K-维数就比较复杂了，首先要找到前10000个两个不等质数之积，在对质数表和两个质数积表进行扫描，找到第n个值。
 
这道题需要注定的还有最后的结果肯定是一个超出64位的整数，需要使用高精度进行幂的运算。

code：

  1#include<iostream>
  2#include<cmath>
  3using namespace std;
  4
  5const int maxn=500000;
  6const int mod=100000000;
  7
  8int prime[maxn];
  9int flag[maxn];
 10int px[10006];
 11int n,K,mark;
 12
 13struct bign
 14{
 15    __int64 val[1000];
 16    int len;
 17    bign(){memset(val,0,sizeof(val));len=1;}
 18};
 19bign a,b,c,d,dd,e;
 20
 21int get_pri()
 22{
 23    int i,j,k;
 24    k=0;
 25    memset(flag,0,sizeof(flag));
 26    flag[0]=flag[1]=1;
 27    for(i=2;i<maxn;i++)
 28    {
 29        if(!flag[i])prime[k++]=i;
 30        for(j=0;j<k&&prime[j]*i<maxn;j++)
 31        {
 32            flag[prime[j]*i]=1;
 33            if(i%prime[j]==0)break;
 34        }
 35    }
 36    return k;
 37}
 38
 39void Init(bign &cc,int t)
 40{
 41    int j=0;
 42    
 43    while(t)
 44    {
 45        cc.val[j++]=t%mod;
 46        t/=mod;
 47    }
 48    cc.len=j;
 49    return ;
 50}
 51
 52void multify(bign &aa,bign &bb)
 53{
 54    int i,j;
 55    memset(dd.val,0,sizeof(dd.val));
 56    dd.len =1;
 57    for(i=0;i<aa.len;i++)
 58        for(j=0;j<bb.len;j++)
 59        {
 60            dd.val[i+j]+=aa.val[i]*bb.val[j];
 61            dd.val[i+j+1]+=dd.val[i+j]/mod;
 62            dd.val[i+j]%=mod;
 63        }
 64        
 65        dd.len=aa.len+bb.len;
 66        if(dd.val[dd.len-1]==0)dd.len--;
 67        aa=dd;
 68        return ;
 69}
 70
 71void power(bign &temp,bign &x,int y)
 72{
 73    temp.len=1;
 74    temp.val[0]=1;
 75    while(y)
 76    {
 77        if(y&1)multify(temp,x);
 78        multify(x,x);
 79        y>>=1;
 80    }
 81    return ;
 82}
 83
 84void cal_xx()
 85{
 86    int i,j,k=0,t;
 87    for(i=4;i<=100000;i++)
 88    {    
 89        t=i;
 90        for(j=0;prime[j]*prime[j]<t;j++)
 91        {
 92            if(t%prime[j])continue;
 93            t=t/prime[j];
 94            if(!flag[t])
 95                px[k++]=i;
 96            else break;
 97            if(k==10000)break;
 98        }
 99        if(k==10000)break;
100    }
101}
102
103int cmp(bign &x,bign &y)
104{
105    if(x.len>y.len)return 1;
106    if(x.len<y.len)return -1;
107    int i;
108    for(i=x.len-1;i>=0;i--)
109    {
110        if(x.val[i]>y.val[i])
111            return 1;
112        if(x.val[i]<y.val[i])
113            return -1;
114    }
115    return 0;
116}
117
118void solve( bign &t)
119{
120    int i=0,j=0,k;
121    int f1=0,f2=0;
122    
123    for(k=0;k<n;k++)
124    {   
125        if(!f1)
126        {
127            Init(a,px[i]);
128//          power(a,d,mark-1);
129        }
130        if(!f2)
131        {
132            Init(d,prime[j]);
133            power(b,d,mark+1);
134        }
135        if(cmp(a,b)==1)
136        {  
137            if(k==n-1)e=b;
138            
139            f1=1;f2=0;    j++;
140        }
141        else 
142        {
143            if(k==n-1)e=a;
144            
145            f1=0;f2=1;i++;
146        }
147    }
148    power(t,e,mark-1);
149}
150
151void output(bign &x)
152{
153    int i=x.len;
154//    printf("  %d\n",i);
155    printf("%d",x.val[--i]);
156    while(i)
157    {
158        printf("%08d",x.val[--i]);
159    }
160    printf("\n");
161}
162
163int main()
164{     
165    get_pri();
166    cal_xx();
167    while(EOF!=scanf("%d%d",&n,&K))
168    {
169        if(K==1){printf("1\n");continue;}
170        
171        mark=0;
172        
173        if(flag[K]){mark=(int)sqrt(K*1.0);}
174        
175        if(!mark)
176        {   
177            Init(d,prime[n-1]);
178            power(c,d,K-1);
179            output(c);
180        }
181        else
182        { 
183            solve(c);
184            output(c);
185        }          
186    }
187    return 0;
188}
189