Educational Codeforces Round 144 (Rated for Div. 2) C - Maximum Set

传送门

题意：

对于一个集合，如果它的任意两个元素都能 有 其中一个能整除另一个，那么它是好的。问在区间[L,R] 中由这个区间某些数内构成的好的集合的最长长度是多少，以及且满足这个长度的好集合有多少个。（懒得想就借鉴了j宝的题面,感兴趣的也可以看看）。

思路
让我们首先考虑怎么获得他的最长的长度，对于集合中任意相邻的两个数中，相差的倍数一定为质数（合数可以由质数的乘机得到），而且一定是最小的质数2，那么可以从l出发，不断的×2知道小于r为止，此时这个数为p，得到的长度即为最长的长度。

然后从最长的长度sum来分析，里面包含的数可以简要概括为
(l,2×l, 4×l,8×l，…)那么如果我们想在其中改变数字以获得更多的满足条件的序列的话，那么我们只需要从两部分分析：序列中只有二和序列中只有一个三的情况（如果有大于3或者两个以上的三的情况那么都可以转变为更多的2的情况那么就不符合条件）。

1.序列中全部为2的情况，那么能改变的就只有l，l通过不断的累加然后去找到一个最大的L满足L+p/l<=r，那么L<=r-p/l,
然后满足条件的序列的数量就为sum2=L-l+1，这就是全为2的情况。
2.序列中有一个3的情况，那么就相当于p里面少了个因子2，多了个因子三，然后继续去寻找最大的L即可。具体看代码.

ps：如果l*2>r满足的话，那么就说明l连一个因子2也加入不进去，那么长度就为 1，数量就为区间和，输出即可。

代码

void slove( )
{int l,r;cin>>l>>r;int p=l;int sum=1;if(l*2>r){cout<<1<<" "<<r-l+1<<endl;return ;}while(p*2<=r){p*=2,sum++;}p/=l;ll sum2=max(0,r/p-l+1);p/=2;p*=3;ll sum3=max(0,r/p-l+1);cout<<sum<<" "<< sum2+sum3*(sum-1)<<endl;
}