Bzoj1257 [CQOI2007]余数之和sum

Time Limit: 5 Sec Memory Limit: 162 MB
Submit: 3949 Solved: 1834

Description

给出正整数n和k，计算j(n, k)=k mod 1 + k mod 2 + k mod 3 + … + k mod n的值，其中k mod i表示k除以i的余数。例如j(5, 3)=3 mod 1 + 3 mod 2 + 3 mod 3 + 3 mod 4 + 3 mod 5=0+1+0+3+3=7

Input

输入仅一行，包含两个整数n, k。

Output

输出仅一行，即j(n, k)。

Sample Input

5 3

Sample Output

HINT

50%的数据满足：1<=n, k<=1000 100%的数据满足：1<=n ,k<=10^9

Source

数学　Dirichlet卷积

还是傻傻不会卷积

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<algorithm>
 4 #include<cstring>
 5 #define LL long long
 6 using namespace std;
 7 const int mxn=100010;
 8 int read(){
 9     int x=0,f=1;char ch=getchar();
10     while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
11     while(ch>='0' && ch<='9'){x=x*10-'0'+ch;ch=getchar();}
12     return x*f;
13 }
14 int n,k;
15 int main(){
16     n=read();k=read();
17     LL ans=0;
18     if(n>k)ans=(n-k)*k,n=k;
19     int a,b;
20     cout<<ans<<endl;
21     for(int i=1;i<=n;i=b+1){
22         a=k/i;b=k/a;
23         if(b>n)b=n;
24         ans+=(LL)k*(b-i+1)-(LL)(i+b)*(b-i+1)/2*a;
25     }
26     printf("%lld
",ans);
27     return 0;
28 }

lll