BZOJ1257题解

发表于 | 更新于 | 评论数： | 阅读次数：

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

1
5 3

Output’s eg #1

1
7

说明

对于$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$连续的一段进行计算即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
/* 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;
}

THE END