1.https://ac.nowcoder.com/acm/contest/5523/I

二分+整数分块

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

typedef long long ll;

ll n,m,q;

int check( ll x )
{
    ll sum=0;
    for( int l=1,r;l<=x;l=r+1 )
    {
        r=x/(x/l);
        sum+=1ll*min(x/l,m)*(r-l+1);
    }
    return sum;
}

int main()
{
    cin>>n>>m>>q;
    if( n<m ) swap(n,m);
    while( q-- )
    {
        int k;cin>>k;
        int l=1,r=k,mid;
        while( l<r )
        {
            mid=l+r>>1;
            if( check(mid)<k ) l=mid+1;
            else r=mid;
        }
        printf("%d\n",l);
    }
}

2.https://ac.nowcoder.com/acm/contest/5/A

整数分块+数位处理

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

typedef long long ll;

ll n,m,q,k;

ll read()
{
    ll x=0,f=1;char s=getchar();
    for( ;isdigit(s);x=x*10+s-48,s=getchar());
    return x;
} 

ll mi[10];

ll integer_block( int n,ll x )
{
    ll res=0;
    for( ll l=1,r;l<=n;l=r+1 )
    {
        r=n/(n/l);
        ll tmp=0;
        for( int i=0;i<=9;i++ )
        tmp+=max(0ll,min(r,(x+1)*mi[i]-1)-max(l,x*mi[i])+1);
        res+=(n/l)*tmp;
    }
    return res;
}

int main()
{
    int l=read(),r=read();mi[0]=1;
    for( int i=1;i<=9;i++ ) mi[i]=mi[i-1]*10;

    for( int i=1;i<=9;i++ ) cout<<integer_block(r,i)- integer_block(l-1,i)<<endl;
}

3.https://www.luogu.com.cn/problem/P2261

余数之和 整数分块

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

typedef long long ll;

ll n,m,q,k;

ll Integer_block( ll x )
{
    ll ans=0;
    for( ll l=1,r;l<=n;l=r+1 )
    {
        if( x/l ) r=min(n,x/(x/l));
        else r=n;
        ans+=(x/l)*(r-l+1)*(l+r)/2;
    }
    return ans;
} 

int main()
{
    cin>>n>>k;
    ll ans=n*k-Integer_block(k);
    cout<<ans<<endl;
}

4.