Codeforces Gym 100425A Luggage Distribution 二分 数学

A - Luggage Distribution
Time Limit: 20 Sec

Memory Limit: 256 MB

题目连接

http://acm.hust.edu.cn/vjudge/contest/view.action?cid=87493#problem/A

Description

All provident tourists know about low-cost airlines. Those who used them at least once also know that their airfare usually includes neither lunch nor luggage.

Naturally, tourists don't want to overpay luggage fee, therefore they distribute their luggage so that it satisfies all airline requirements.

A certain tourist prepaid three luggage slots. Then he calculated the number of different ways K to distribute weight N among these three slots so that all luggage is packed, none of the slots are empty and all weights are integers. The order of the slots does not matter, so, for example, two distributions 2,  2,  1 and 2,  1,  2 are considered the same.

After landing, the tourist realised that the airline lost all his luggage! And while filling in a lost and found application, he found out that he does not remember the weight of each slot. He remembered only the fact that the number of ways K to pack the luggage was at least Land did not exceed R.

You need to calculate number of possible integer total weights N that could have been in the tourist's luggage.

 

Input

The single line of input holds two integer numbers  L and R (1 ≤ L ≤ R ≤ 10¹⁷): the minimum and maximum number of ways to distribule the luggage in three slots.

Output

Output a single integer: the number of possible total weigths  N that could have been carried by the tourist.

Sample Input

2 4

Sample Output

3

HINT

 

题意

对于一个数，分成三个数的不同分法有多少种。

但是题目并不问这个，而是问，给你L,R的方案数，问你分法为这么多的数有多少个

题解：

先打表，然后推公式，推出来之后再二分就好了

代码：

//qscqesze
#include <cstdio>
#include <cmath>
#include <cstring>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <set>
#include <vector>
#include <sstream>
#include <queue>
#include <typeinfo>
#include <fstream>
#include <map>
#include <stack>
typedef unsigned long long ll;
using namespace std;
//freopen("D.in","r",stdin);
//freopen("D.out","w",stdout);
#define sspeed ios_base::sync_with_stdio(0);cin.tie(0)
#define maxn 1005000
#define mod 10007
#define eps 1e-6
int Num;
//const int inf=0x7fffffff;   //нчоч╢С
const int inf=0x3f3f3f3f;
inline ll read()
{
    ll x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
//**************************************************************************************

ll get1(ll x)
{
    ll ans=(ceil)(((x-3)*(x-3)*1.0)/12*1.0+(x-3)*1.0/2.0);
    if((x-3)%6==0)
        ans++;
    return ans;
}
ll get(ll x)
{
    ll ans=(x-3)*(x+3);
    if(ans%12LL==0) ans/=12LL;else ans=ans/12LL+1LL;
    if((x-3)%6==0)
        ans++;
    return ans;
}

ll solve(ll x)
{
    ll l=3,r=0x7fffffffLL;
    while(l<=r)
    {
        ll mid=(l+r)/2;
        ll G=get(mid);
        if(G<x)
            l=mid+1;
        else
            r=mid-1;
    }
    return l;
}
int main()
{
    ll l,r;
    cin>>l>>r;
    ll a1=solve(l);
    ll a2=solve(r);
    if(get(a2)>r)
        a2--;
    if(r==1)
        a2++;
    cout<<a2-a1+1<<endl;
}