题意：A和B玩一个游戏：A在[L,R]之间随机选取一个数X，之后由B来猜这个数，
如果猜的数比X小，则A就告诉B你猜的数小了，
如果猜的数等于X则游戏结束，
如果猜的数大于X，则在这之后A只会回答B是否猜对了，而不会告诉B是否猜小了。
问:在最坏的情况下，B猜到X时最少需要猜多少次，并输出方案数对100000073取模
L,R<=5e6
思路：少了蛋数量的鹰蛋……
f[i]表示长度为i的区间需要的询问次数
p[i]表示至少需要i次询问的最短区间长度
a[i]表示区间长度为i的最优选择方案数
i可以由[i-f[i],p[f[i]]-1]转移而来
i-f[i]是还剩f[i]次机会，每次选择猜的数+1
p[f[i]]-1是需要测试f[i]-1次的最大区间长度
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<cmath>
#include<bitset>
typedef long long ll;
using namespace std;
#define N 5100000
#define oo 10000000
#define MOD 100000073 int f[N],p[N],a[N],s[N]; int main()
{
for(int i=;i*(i+)/<N;i++)
for(int j=i*(i-)/+;j<=i*(i+)/;j++) f[j]=i;
for(int i=;i*(i-)/+<N;i++) p[i]=i*(i-)/+;
a[]=a[]=;
a[]=;
s[]=; s[]=;
for(int i=;i<N;i++)
{
int x=i-f[i];
int y=p[f[i]]-;
a[i]=(s[y]-s[x-]+MOD)%MOD;
s[i]=(s[i-]+a[i])%MOD;
}
int x,y;
while(scanf("%d%d",&x,&y)!=EOF) printf("%d %d\n",f[y-x+],a[y-x+]);
return ;
}