NEERC2005 - Joseph

张文泰 posted @ 2010年1月18日 20:21 in Art of Science with tags NEERC acm 数列 , 2210 阅读

NEERC2005主页在这里

题目给定n和k,要求$\sum_{i=1}^n(k\mod i)$

我们先找一下规律,发现与等差数列是有关系的。我们对于当前的i,令$p=k\mod i$$q=\left\lfloor\frac{k}{i}\right\rfloor$。那么当i增大1时,如果q不变,p一定减少了q,那么将p一直减小到0,同时对这一段进行求和(用数列求和公式),同时i增大到下一段的开头。

详细情况见代码:

#include <cstdio>
#include <algorithm>

using namespace std;

int n,k;

__int64 sum(int a,int d,int n) {
  return (__int64)(2*a-d*n)*(n+1)/2;
}

int main() {
  freopen("joseph.in","r",stdin);
  freopen("joseph.out","w",stdout);
  scanf("%d%d",&n,&k);
  int i = 1,p,q,a;
  __int64 r = 0;
  while (i<=n) {
    q = k%i; p = k/i;
    if (p>0) a = q/p;
    else a = INT_MAX;
    r += sum(q,p,min(a,n-i));
    i += min(a,n-i)+1;
  }
  printf("%I64d\n",r);
  return 0;
}

本作品遵循“署名-非商业性使用-相同方式共享 3.0 Unported”协议,转载请注明来自richard-desktop
Creative Commons License

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter