HDOJ 3398

本文主要是介绍HDOJ 3398，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

这个题坑了太久太久啊！！！！！贡献了得有30+WA才发现

原来是因为在乘法中有溢出导致一直TLE啊。。。。

但是到最后也不知道有个问题怎么解决的。

就是在getp（）中的num值的诡异的改变！

 

#include<stdio.h>
#include<string.h>
#include<math.h>
typedef long long LL;
const int TON=20100501;
const int max1=2000005;
int p[max1],b[max1]={0},num=0;
void getp()
{
    int i,j;
    for (i=4;i<=max1;i+=2) b[i]=1;
    for (i=3;i*i<=max1;i+=2)
        if (b[i]==0)
        {
          for (j=i*i;j<=max1;j+=i)
            b[j]=1;
        }
      for (i=2;i<=max1;i++)
        if (b[i]==0) p[num++]=i;
}//得到质数表
int getm(int n,int pp)
{
    LL rec=pp;//就是这里！！！！
    int ans=0;
    while(n>=rec)
    {
        ans+=n/rec;
        rec*=pp;
    }
    return ans;
}//求出n！中质因子的指数
LL qpow(int a,int b)
{
    LL ret=a;
    LL ans=1;
    while(b)
    {
        if(b&1) ans=ans*ret%TON;
        ret=ret*ret%TON;
        b/=2;
    }
    return ans;
}//快速幂
int main()
{
    //freopen("data.in","r",stdin);
    int t,n,m;
    int i;
    int tmp;
    int kk;
    LL ret;
    getp();
    scanf("%d",&t);
    while(t--)
    {
        ret=1;
        scanf("%d%d",&n,&m);
        for(i=1;i<num&&p[i]<=m+n;i++)
        {
            kk=n-m+1;
            tmp=getm(m+n,p[i])-getm(m,p[i])-getm(n+1,p[i]);//tmp是整个公式中质因子p【i】的个数
            while(kk%p[i]==0) {tmp++;kk/=p[i];}
            ret=ret*qpow(p[i],tmp)%TON;
        }
        printf("%I64d\n",ret);
    }
    return 0;
}

这篇关于HDOJ 3398的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---