BZOJ 1257: [CQOI2007]余数之和sum【神奇的做法，思维题】

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 typedef long long ll;
 4 inline int read()
 5 {
 6     int x=0,f=1;
 7     char ch=getchar();
 8     while(ch<'0'||ch>'9')
 9     {
10         if(ch=='-')
11             f=-1;
12         ch=getchar();
13     }
14     while(ch>='0'&&ch<='9')
15     {
16         x=x*10+ch-'0';
17         ch=getchar();
18     }
19     return x*f;
20 }
21 int n,k;
22 ll ans;
23 int main()
24 {
25     n=read();
26     k=read();
27     if(n>k)
28     {
29         ans=(ll)(n-k)*k;
30         n=k;
31     }
32     int r;
33     for(int i=1;i<=n;i=r+1)
34     {
35         int t=k/i;
36         r=k/t;
37         if(r>=n)r=n;
38         ans+=(ll)(r-i+1)*k-(ll)(r-i+1)*(i+r)/2*t;
39     }
40     printf("%lld\n",ans);
41     return 0;
42 }