乞讨间隔[a，b]在见面p^k*q*^m(k>m)中数号码-白红宇

乞讨间隔[a，b]在见面p^k*q*^m(k>m)中数号码

阅读量：5099 次

发布时间：2019-06-13

本文共 1375 字，大约阅读时间需要 4 分钟。

标题叙述性说明：

1<=a,b<=10^18,p,q他们是素数 2<=p,q<=10^9;

求在[a,b]内能够表示为 x*p^k*q^m k > m 的数的个数

分析：

因为要小于b。因此m一定小于 log10(b)/log10(p*q);

因此我们能够枚举m。中间计数的时候须要用到容斥。

详细看代码：

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #include 
         
          using namespace std;typedef long long LL;LL mypow(LL a,int b){    LL ans = 1;    while(b){        if(b&1){            ans=ans*a;            b--;        }        b>>=1;        a=a*a;    }    return ans;}int main(){    LL a,b,p,q;    while(~scanf("%lld%lld%lld%lld",&a,&b,&p,&q)){        int mmax = log10(b*1.0)/log10(p*q*1.0)+1;        LL ans = 0;        for(int i=0;i<=mmax;i++){            if(mypow(p,i+1)>b*1.0/mypow(q,i))//防止爆long long                break;            for(int j=i+1;j<64;j++){                if(mypow(p,j)>b*1.0/mypow(q,i)) break;//防止爆long long                LL tmp=mypow(p,j)*mypow(q,i);                LL cnt1 = b/tmp,cnt2=(a-1)/tmp;//因为是闭区间 因此要用a-1;                ans += cnt1;                ans -= cnt2;                ans -= cnt1/p;                ans -= cnt1/q;                ans += cnt1/p/q;                ans += cnt2/p;                ans += cnt2/q;                ans -=cnt2/p/q;            }        }        printf("%lld\n",ans);    }    return 0;}