希尔伯特旅馆悖论

题目连接：http://acm.bupt.edu.cn/onlinejudge/newoj/showProblem/ProblemList.php?problem_name=%E5%B8%8C%E5%B0%94%E4%BC%AF%E7%89%B9%E6%97%85%E9%A6%86%E6%82%96%E8%AE%BA

很简单的题目，题目中给了解法，直接打完素数表，快速幂模即可。

题目的解法就是：输入x，y只要求第x+1个素数的y次方mod mo就是结果

代码：

#include <iostream>
#include <cmath>

using namespace std;

const int N=1100000;
const int M=90000;
const int mo=100000007;
bool is[N];int prm[M];

int getprm(int n)
{
    int i, j, k = 0;
    int s, e = (int)(sqrt(0.0 + n) + 1);
    memset(is, 1, sizeof(is));
    prm[k++] = 2;
    is[0] = is[1] = 0;
    for (i = 4; i < n; i += 2) is[i] = 0;
    for (i = 3; i < e; i += 2) if (is[i])
        {
            prm[k++] = i;
            for (s = i * 2, j = i * i; j < n; j += s)
                is[j] = 0;
        }
    for ( ; i < n; i += 2) if (is[i]) prm[k++] = i;
    return k; // 返回素数的个数
}


long long powmod(long long a,long long p)//快速幂模模板 a为基数p为幂 mo为全局的模即a^p mod mo
{
    long long r=1;
    while(p>0)
    {
        if(p&1)r=r*a%mo;
        a=a*a%mo;
        p=p/2;
    }
    return r;
}


int main()
{
    int t;
    scanf("%d",&t);
    getprm(N);
    //printf("%d\n",k);
    while(t--){
        int x,y;
        scanf("%d%d",&x,&y);
        long long ans=powmod(prm[x],y);
        printf("%lld\n",ans);
    }
    return 0;
}