UVA 1363 - Joseph's Problem
题意:给定n, k,求出∑ni=1(k mod i)
思路:因为n和k都非常大。直接暴力是行不通的。然后在纸上画了一些情况,就发现事实上对于k/i同样的那些项是形成等差数列的。于是就能够把整个序列进行拆分成[k,k/2],[k/2, k/3], [k/3,k/4]...k[k/a, k/b]这种等差数列,利用大步小步算法思想。这里a枚举到sqrt(k)就能够了。这样就还剩下[1,k/a]的序列须要去枚举,总时间复杂度为O(sqrt(k)),然后注意对于n大于k的情况,n超过k的部分全是等于k。为(n - k) * k,这样把全部部分加起来就是答案
代码:
#include <stdio.h> #include <string.h> #include <math.h> long long n, k; long long solve() { long long ans = 0; if (n > k) ans += (n - k) * k; long long a = (long long )sqrt(k), b = k / a; for (long long i = a; i > 1; i--) { long long a0 = k / i, an = k / (i - 1); if (a0 > n) break; if (an > n) an = n; ans += (k % an + k % (a0 + 1)) * (an - a0) / 2; } for (int i = 1; i <= n && i <= b; i++) ans += k % i; return ans; } int main() { while (~scanf("%lld%lld", &n, &k)) { printf("%lld ", solve()); } return 0; }