洛谷 - P2261 - 余数求和

https://www.luogu.org/problemnew/show/P2261

看了一下题解，取模运算可以换成减法来做。 $a\%b=a-b*\lfloor\frac{a}{b}\rfloor$ ，所以求和式可以化简，然后用数论分块来搞。

#include<bits/stdc++.h>

using namespace std;

#define ll long long

int main() {

    ll n,k;

    scanf("%lld%lld",&n,&k);

    ll ans=n*k;

    for(ll l=,r; l<=n; l=r+) {

        if(k/l!=) {

            r=min(k/(k/l),n);

        } else {

            //k/l==0，意味着l>k，所有的后面的下整都是0，分成同一块

            r=n;

            break;

        }

        ans-=(k/l)*(r-l+)*(l+r)/;

    }

    printf("%lld",ans);

    return ;

}

巴特西

洛谷 - P2261 - 余数求和

最新文章

热门文章