首页 > 代码库 > UVa 1363 (数论 数列求和) Joseph's Problem
UVa 1363 (数论 数列求和) Joseph's Problem
题意：
给出n, k，求
分析：
假设，则k mod (i+1) = k - (i+1)*p = k - i*p - p = k mod i - p
则对于某个区间，i∈[l, r]，k/i的整数部分p相同，则其余数成等差数列，公差为-p
然后我想到了做莫比乌斯反演时候有个分块加速，在区间[i, n / (n / i)]，n/i的整数部分相同，于是有了这份代码。
1 #include <cstdio> 2 #include <algorithm> 3 using namespace std; 4 typedef long long LL; 5 6 int main() 7 { 8 LL n, k; 9 while(scanf("%lld%lld", &n, &k) == 2)10 {11 LL ans = 0;12 LL i, j, r = min(n, k);13 for(i = 1; i <= r; i = j + 1)14 {15 j = k / (k / i);16 if(j > r) j = r;17 18 LL d = -k / i;19 LL l = j - i + 1;20 LL a1 = k % i;21 ans += (LL) (a1*l + l*(l-1)/2*d);22 }23 if(n > k)24 ans += (LL) (n-k) * k;25 26 printf("%lld\n", ans);27 }28 29 return 0;30 }
后来试了一下lrj的代码，比我的短还比我的快，给跪了
1 // UVa1363 Joseph‘s Problem 2 // Rujia Liu 3 #include<iostream> 4 #include<algorithm> 5 using namespace std; 6 7 // 首项为a，公差为-d，除了首项之外还有n项 8 // 末项为a-n*d，平均数为(2*a-n*d)/2 9 long long sum(int a, int d, int n) {10 return (long long)(2*a-n*d)*(n+1)/2;11 }12 13 int main() {14 int n, k;15 while(cin >> n >> k) {16 int i = 1;17 long long ans = 0;18 while(i <= n) {19 int q = k % i, p = k / i;20 int cnt = n - i; // 最多还有n - i项21 if(p > 0) cnt = min(cnt, q / p); 22 ans += sum(q, p, cnt);23 i += cnt + 1;24 }25 cout << ans << "\n";26 }27 return 0;28 }
UVa 1363 (数论 数列求和) Joseph's Problem
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。