SRM505 Div1 Medium(500) SetMultiples

TopCoder

SetMultiples

閾値Tより小さい値は１個ずつSに含まれるかどうかを調べる。

閾値T以上の値は、[A,B], [C,D]の範囲から、[(A+1)/2,B/2],[(C+1)/2,D/2],[(A+2)/3,B/3],[(C+2)/3,D/3],……,[(A+k-1)/k,B/k],[(C+k-1)/k,D/k]を除いた範囲の長さを調べる。T以上と[A,B],[C,D]で+1、[(A+1)/2,B/2],……で-1すると、2となる範囲が答え。

#include <vector>
#include <utility>
#include <algorithm>
using namespace std;

class SetMultiples{public:
long long smallestSubset( long long A, long long B, long long C, long long D )
{
    long long ans = 0;
    long long T = 100000;
    
    //  T未満
    for ( long long i=A; i<=B && i<T; i++ )
        if ( B<2*i && C%i!=0 && C/i==D/i )
            ans++;
    for ( long long i=C; i<=D && i<T; i++ )
        if ( D<2*i )
            ans++;

    //  T以上
    vector<pair<long long,int> > P;
    P.push_back( make_pair(T,   1) );
    P.push_back( make_pair(A,   1) );
    P.push_back( make_pair(B+1,-1) );
    P.push_back( make_pair(C,   1) );
    P.push_back( make_pair(D+1,-1) );
    for ( long long i=2; B/i>=T; i++ )
        P.push_back( make_pair((A+i-1)/i, -1) ),
        P.push_back( make_pair(B/i+1,      1) );
    for ( long long i=2; D/i>=T; i++ )
        P.push_back( make_pair((C+i-1)/i, -1) ),
        P.push_back( make_pair(D/i+1,      1) );
    sort(P.begin(),P.end());

    int t = 0;
    for ( int i=0; i<(int)P.size(); i++ )
    {
        if ( t == 2 )
            ans += P[i].first-P[i-1].first;
        t += P[i].second;
    }

    return ans;
}};