作者:aofeng12_313 | 来源:互联网 | 2023-01-26 00:01
题意:给了x,y,l,r,求由x,y可以线性组合出多少个在[l,r]内的数。例x4,y5,l7,r13,则x,y可以组合出8,9,10,12,13解:所有x,y线性组合的数可化
题意:给了x,y,l,r,求由x,y可以线性组合出多少个在[l,r]内的数。例x=4,y=5,l=7,r=13,则x,y可以组合出8,9,10,12,13
解:所有x,y线性组合的数可化为区间[x,y],[2x,2y],[3x,3y]......
从[kx,ky]开始区间重叠,则(k+1)x<=ky计算出k,k之前的区间均分离
在[l,r]区间内的数可化为f[r]-f[l-1],f[x]为x之前由x,y线性组合的数的个数
#include
#include
#include
using namespace std;
typedef long long ll;
ll sox(ll x,ll y,ll z,ll k)
{
ll tempx=0,tempy=z;
while(tempx<=tempy) //找到第一个ky>z的区间
{
ll m=(tempx+tempy)/2;
if(((double)m*y)>=z)
tempy=m-1;
else
tempx=m+1;
}
if(tempx<=k)
return (y-x)*tempx*(tempx-1)/2+(tempx-1)+(tempx*x>z?0:z-tempx*x+1); //区间计算为k之前的:(y-x+1)+(2y-2x+1)+...+((k-1)y-(k-1)x+1),之后的区间为z-kx
else
return (y-x)*k*(k-1)/2+(k-1)+(k*x>z?0:z-k*x+1);
}
ll fff(ll x,ll y,ll l,ll r)
{
ll t=y/(y-x); //找到(k+1)x<=ky的区间
if(y%(y-x))
t++;
return sox(x,y,r,t-1)-sox(x,y,l-1,t-1);
}
int main()
{
ll x,y,l,r;
while(cin>>x>>y>>l>>r)
{
if(r
版权声明:本文为博主原创文章,未经博主允许不得转载。
URAL 1720 Summit Online Judge