首页 > 代码库 > 求 区间[a,b]内满足p^k*q*^m(k>m)的数的个数
求 区间[a,b]内满足p^k*q*^m(k>m)的数的个数
题目描述:
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 <iostream> #include <cstdio> #include <cmath> #include <cstring> #include <algorithm> 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; }
求 区间[a,b]内满足p^k*q*^m(k>m)的数的个数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。