Codeforces Round #701 (Div. 2) C. Floor and Mod

題意

給定 x , y x,y x,y，詢問當 1 ≤ a ≤ x , 1 ≤ b ≤ y 1\le a\le x,\ 1\le b\le y 1≤a≤x, 1≤b≤y時， ? a b ? = a m o d b \lfloor \frac a b \rfloor=a\ mod\ b ?ba??=a mod b的對數

限制

1 ≤ x , y ≤ 1 0 9 1\le x,y\le 10^9 1≤x,y≤109

思路

（想法有很多種，本文主要通過分塊求解）

（并沒有那么難，但為什么總是往難的方向想呢……）

讀懂題意后如果用公式化簡

根據 a m o d b = a ? ? a b ? ? b a\ mod\ b=a-\lfloor \frac a b \rfloor*b a mod b=a??ba???b，最多只能夠化到 a = ( b + 1 ) ? ? a b ? a=(b+1)*\lfloor \frac a b \rfloor a=(b+1)??ba??

可得 a b + 1 = ? a b ? \frac a {b+1}=\lfloor \frac a b \rfloor b+1a?=?ba??

明顯， b + 1 b+1 b+1一定是 a a a的因子

（然后就想不到其他規律了）

那么我們列舉 b b b，再列舉 b + 1 b+1 b+1的倍數進行打表

得到規律：

對于任意大于 2 2 2的正整數 b b b

滿足題意的 a a a最多有 b ? 1 b-1 b?1項，每一項都是 b + 1 b+1 b+1的倍數，最大項為 ( b ? 1 ) ? ( b + 1 ) (b-1)*(b+1) (b?1)?(b+1)

所以對于每個 b b b，我們可以先求出 1 1 1到 x x x內有多少 b + 1 b+1 b+1的倍數（即 ? x b + 1 ? \lfloor\frac x {b+1}\rfloor ?b+1x??個）

在計算答案時，根據規律需要將其與 b ? 1 b-1 b?1取小

但是這種方法的時間復雜度為 O ( y = 1 0 9 ) O(y=10^9) O(y=109)，不可行

考慮優化，發現如果 ( b ? 1 ) ? ( b + 1 ) > x (b-1)*(b+1)\gt x (b?1)?(b+1)>x，即 ? x b + 1 ? < b ? 1 \lfloor\frac x {b+1}\rfloor \lt b-1 ?b+1x??<b?1時

受 x x x的限制，會有一段段連續的 b b b對應的答案數量相同，且答案均為 ? x b + 1 ? \lfloor\frac x {b+1}\rfloor ?b+1x??

直接考慮分塊，令 t = ? x b + 1 ? t=\lfloor\frac x {b+1}\rfloor t=?b+1x??表示當前段的答案，再通過 ? x t ? \lfloor\frac x t\rfloor ?tx??來求出滿足答案為 t t t的最大的 b + 1 b+1 b+1的值

故此時最大的 b b b應為 ? x t ? ? 1 \lfloor\frac x t\rfloor-1 ?tx???1，注意與 y y y取小即可

該段的答案即段長度*t，其后讓 b b b直接成為右端點 + 1 +1 +1即可

當 ( b ? 1 ) ? ( b + 1 ) ≤ x (b-1)*(b+1)\le x (b?1)?(b+1)≤x時，對于每個 b b b的答案數量均為 b ? 1 b-1 b?1

故我們可以求出滿足 ( b ? 1 ) ? ( b + 1 ) ≤ x (b-1)*(b+1)\le x (b?1)?(b+1)≤x以及 b ≤ y b\le y b≤y的最大的 b b b

那么答案就是 1 + 2 + 3 + ? + ( b ? 1 ) 1+2+3+\cdots +(b-1) 1+2+3+?+(b?1)，直接等差求和公式即可

對于這個最大的滿足 ( b ? 1 ) ? ( b + 1 ) ≤ x (b-1)*(b+1)\le x (b?1)?(b+1)≤x的 b b b，先忽略條件 b ≤ y b\le y b≤y，結論是 m a x b = ? x ? maxb=\lfloor\sqrt x\rfloor maxb=?x ??或 m a x b = ? x ? + 1 maxb=\lfloor\sqrt x\rfloor +1 maxb=?x ??+1

或者這里也可以打表找規律

對于 m a x b + 1 maxb+1 maxb+1到 y y y，還是分塊處理

代碼

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

void solve()
{
    int x,y;
    scanf("%d%d",&x,&y);
    
    int b=sqrt(x)+1;
    if(1LL*(b-1)*(b+1)>x)
        b--;
    b=min(b,y); //注意與y取小
    ll ans=1LL*b*(b-1)/2;
    
    for(b++;b<=y;)
    {
        int t=x/(b+1);
        if(t==0)
            break;
        
        int nxt=min(x/t-1,y); // 注意x/t是對于b+1的最大值
        ans+=1LL*(nxt-b+1)*t;
        
        b=nxt+1;
    }
    printf("%lld\n",ans);
}
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
        solve();
    return 0;
}

To cnblogs