C. Floor and Mod (分块整除)

系统管理员 2021-07-16 12:00 503阅读 0赞

题目

a/b=i, a%b=i -> a=i*(b+1)，(对于一个b可以配出几个i就可以产生几个贡献)可以知道对于给出的x,y 取任意1<=b<=y，一个b产生的贡献为min(x/(b+1)，b-1)

当x>=(b+1)(b-1)时对于此时的b的贡献全取b-1

当x<(b+1)(b-1)时按x/(b+1)的贡献，此时用整除分块求解

另注意下范围，细节见代码

Code:

#include<iostream>
#include<cmath>
#define FAST ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
using namespace std;
typedef long long ll;
int main()
{ 
    FAST;
    int t;cin >> t;
    while (t--)
    { 
        ll a, b;cin >> a >> b;
        ll ans = 0;
        for (ll l = max(2.0,ceil(sqrt((double)a-1.0)))+1, r;l <= min(a,b+1);l = r + 1)
        { 
            r = a / (a / (l));
            if (r >= min(a, b+1))
            { 
                r = min(a, b+1);
                ans += (r - l + 1) * (a / l);
                break;
            }
            ans += (r - l +1) * (a / (l));
        }
        ll k = min((double)b-1,max(2.0, ceil(sqrt((double)a - 1.0)))-1-1);
        ans += (1 + k) * k / 2;
        cout << ans << endl;
    }
}