题目很简单，你的解答也很简单：    int calc(int n,int k){     int ret = 0,i;    for (i = 1; i <= n; i++)ret += k%i;    return ret;}   可是，它怎么就超时了呢？ 注意约束条件： The input file contains n and k(1<= n,k <= 10^9). n的最大值是10^9。。。。你的程序不超时才怪呢？ O(n)的算法，还能怎么优化呢？ 对给定的K，所求为不大于n的所有正整数除K的余数r1,r2,......,rn的总和。假设它们对应的商为s1,s2,.....,sn. 注意到，商的可能取值只有O(sqrt(n))种情况，对每个可能的商的值，k%i成等差数列。容易看出，此问题的解的时间复杂度不大于O(sqrt(n)). 分析，解决问题    对N，K比较小的情况，写出具体的余数和商数表。   观察，分析这个表格。   现在，你能否为本问题设计出复杂度为O(sqrt(n))的算法？

评论