CQOIX2007余数之和

朴素能得个差不多吧……

这题改进算法真恶心

pascal一直过不了，难道非得转c++？

代码：（pascal）

 1 var n,k,i,l,r,m:longint;
 2     ans:qword;
 3 function ceil(x:real):longint;
 4  begin
 5  if trunc(x)<x then exit(trunc(x)+1) else exit(trunc(x));
 6  end;
 7 procedure main;
 8  begin
 9    readln(n,k);
10    ans:=0;
11    if n>k then
12     begin
13      inc(ans,(n-k)*k);
14      n:=k;
15     end;
16    m:=ceil(sqrt(k));
17    for i:=1 to m do inc(ans,k mod i);
18    for i:=1 to m do
19     begin
20       l:=(k div (i+1))+1;
21       r:=(k div i);
22       if l<=m then l:=m+1;
23       if r>n then r:=n;
24       if r<l then continue;
25       inc(ans,(((k<<1)-i*(l+r))*(r-l+1)>>1));
26     end;
27    writeln(ans);
28  end;
29 begin
30   main;
31 end.

View Code

代码：（c++）

 1 #include <iostream>
 2 #include <cmath>
 3 using namespace std;
 4 
 5 long long ans,n,k;
 6 int main() {
 7   ios::sync_with_stdio(false);
 8   cin>>n>>k;
 9   if (n>k) {
10     ans+=k*(n-k);
11     n=k;
12   }
13   long long sqrtk=ceil(sqrt(k));
14   for (long long i=1;i<=sqrtk;++i) ans+=k%i;
15   for (long long a=1;a<=sqrtk;++a) {
16     long long L=floor(k/(a+1))+1;
17     long long R=floor(k/a);
18     if (L<=sqrtk) L=sqrtk+1;
19     if (R>n) R=n;
20     if (R<L) continue;
21     ans+=((k<<1)-a*L-a*R)*(R-L+1)>>1;
22   }
23   cout<<ans;
24 }

View Code

另一种分块方法，pascal还是过不了……

 1 #include <cmath>
 2 #include <cstdio>
 3 #include <algorithm>
 4 
 5 long long n, k, ans;
 6 int main()
 7 {
 8   scanf("%lld%lld", &n, &k);
 9   if (n > k)
10   {
11     ans += (n-k)*k;
12     n = k;
13   }
14   ans += n * k;
15   for (long long i = 1, last; i <= n; i = last+1)
16   {
17     last = std::min(n, k/(k/i));
18     ans -= (k/i) * (i+last) * (last-i+1) / 2;
19   }
20   printf("%lld", ans);
21 }

View Code