覆盖数字的数量 51Nod - 1131

本文主要是介绍覆盖数字的数量 51Nod - 1131，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://www.51nod.com/Challenge/Problem.html#!#problemId=1131

用[a,b]之间的这些数 可以表示的数的范围是[a,b] [2a,2b]...[ka,kb]... 随着k增大 这些区间很快就会出现相交的情况 这样后边的所有数就全都可以表示了 两区间相交时有k*b>=(k+1)*a-1 k>=(a-1)/(b-a) 这里的k即为需要计算的区间数量 因为这之前的区间都是不相交的 如果a很大 那区间左端点k*a很快就会超过给定的y 如果a很小 那不相交的区间也很少 暴力即可

 

 

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;ll solve(ll l1,ll r1,ll l2,ll r2)
{return max(0ll,min(r1,r2)-max(l1,l2)+1);
}int main()
{ll a,b,x,y,i,ans;int t;scanf("%d",&t);while(t--){scanf("%lld%lld%lld%lld",&a,&b,&x,&y);ans=0;for(i=1;i*b<(i+1)*a-1&&i*a<=y;i++){ans+=solve(i*a,i*b,x,y);}if(i*a<=y) ans+=(y-max(x,i*a)+1);printf("%lld\n",ans);}return 0;
}

 

这篇关于覆盖数字的数量 51Nod - 1131的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---