BZOJ复活了呢QAQ。

题目描述

求映射 $f(x,k) \to \sum_{i=1}^x k \;mod \;i$ 的值。

输入输出格式

输入格式

两个整数， $n,k$ 。

输出格式

$f(n,k)$

INPUT & OUTPUT’s examples

Input’s eg #1

5 3

Output’s eg #1

说明

对于 $100 \%$ 的数据， $1 \leq n,k \leq 10^9$

分析

为了更好地理解题意，我把题面魔改了一下（雾

我们来看 $f(x,k)$ 这个函数：

$f(x,k) = \sum_{i=1}^x k \; mod \; i$

因为，

$a \;mod \;b = a - \lfloor \frac{a}{b} \rfloor \times b$

所以，原式可以化简，得：

$f(x,k) = \sum_{i=1}^x k - \lfloor \frac{k}{i} \rfloor \times i$

继续化简：

$f(x,k) = x \times k - \sum_{i=1}^x \lfloor \frac{k}{i} \rfloor \times i$

我们知道 $\lfloor \frac{k}{i} \rfloor$ 至多有 $\sqrt{k}$ 种取值。

那么我们对 $\lfloor \frac{k}{i} \rfloor$ 连续的一段进行计算即可。

代码

/* Headers */
#include<cstdio>
#include<cstring>
#include<cmath>
#include<cctype>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#define FOR(i,a,b,c) for(int i=(a);i<=(b);i+=(c))
#define ROF(i,a,b,c) for(int i=(a);i>=(b);i-=(c))
#define FILE_IN(x) freopen(x,"r",stdin);
#define FILE_OUT(x) freopen(x,"w",stdout);
#define CLOSE_IN() fclose(stdin);
#define CLOSE_OUT() fclose(stdout);
namespace FastIO{
    const int BUFSIZE=1<<20;
    char ibuf[BUFSIZE],*is=ibuf,*its=ibuf;
    char obuf[BUFSIZE],*os=obuf,*ot=obuf+BUFSIZE;
    inline char getch(){
        if(is==its)
            its=(is=ibuf)+fread(ibuf,1,BUFSIZE,stdin);
        return (is==its)?EOF:*is++;
    }
    inline int getint(){
        int res=0,neg=0,ch=getch();
        while(!(isdigit(ch)||ch=='-')&&ch!=EOF)
            ch=getch();
        if(ch=='-'){
            neg=1;ch=getch();
        }
        while(isdigit(ch)){
            res=(res<<3)+(res<<1)+(ch-'0');
            ch=getch();
        }
        return neg?-res:res;
    }
    inline void flush(){
        fwrite(obuf,1,os-obuf,stdout);
        os=obuf;
    }
    inline void putch(char ch){
        *os++=ch;
        if(os==ot)	flush();
    }
    inline void putint(int res){
        static char q[10];
        if(res==0)	putch('0');
        else if(res<0){
            putch('-');
            res=-res;
        } 
        int top=0;
        while(res){
            q[top++]=res%10+'0';
            res/=10;
        }
        while(top--)	putch(q[top]);
    }
} 
inline void read(int &x){
	int rt = FastIO::getint();
	x = rt;
}
inline void print(int x){
	FastIO::putint(x);
	FastIO::flush();
} 
/* definitions */
int n,k;
ll ans;
/* functions */
int main(){
	read(n);read(k);
	if(n>k)ans=(ll)(n-k)*k,n=k;
	int r;
	for(int i=1;i<=n;i=r+1){
		int t=k/i;r=k/t;
		if(r>=n)r=n;
		ans+=(ll)(r-i+1)*k-(ll)(r-i+1)*(i+r)/2*t;
	}
	printf("%lld\n",ans);
	return 0;
}

BZOJ1257题解