首页 > 代码库 > UVA 1363 Joseph's Problem 找规律+推导 给定n,k;求k%[1,n]的和。
UVA 1363 Joseph's Problem 找规律+推导 给定n,k;求k%[1,n]的和。
/** 题目:Joseph‘s Problem 链接:https://vjudge.net/problem/UVA-1363 题意:给定n,k;求k%[1,n]的和。 思路: 没想出来,看了lrj的想法才明白。 我一开始往素数筛那种类似做法想。 想k%[1,n]的结果会有很多重复的,来想办法优化。 但没走通。 果然要往深处想。 通过观察数据发现有等差数列。直接观察很难确定具体规律;此处应该想到用式子往这个方向推导试一试。 lrj想法: 设:p = k/i; 则:k%i = k-i*p; 容易想到有可能k/i==k/(i+1) 当k/i=k/(i+1); k%(i+1) = k-(i+1)*p = k - i*p - p = k%i - p; 发现等差。 如果k/j = k/i = p; 那么[i,j]区间内的值为一个等差数列。等差为-p; 如何求最大的j呢? j = k/p; 项数n = j-i+1 = k/p - i + 1 = (k-i*p)/p + 1 = (k%i)/(k/i) + 1; 首项:a1 = k%i; 公差:d = -p = -k/i; 当d = 0;说明后面的结果全部相同等于a1; 当d > 0;按照上述推导计算. */ #include <iostream> #include <cstdio> using namespace std; typedef long long ll; typedef unsigned long long ull; ull getSum(ull a1,ull n,ull d) { ull sum = 0; sum = n*a1+n*(n-1)/2*d; return sum; } int main() { int n, k; while(scanf("%d%d",&n,&k)==2) { ull a1, m, d; ull ans = 0; for(int i = 1; i <= n; i+=m){ a1 = k%i; d = -k/i; if(d==0){ ans += (ull)(n-i+1)*k; break; } m = a1/(k/i)+1; m = min(m,ull(n-i+1));///k >> n的时候,不要计算多出来的结果。 ans += getSum(a1,m,d); } printf("%llu\n",ans); /*ans = 0; for(int i = 1; i <= n; i++){ ans += k%i; printf("%d\n",k%i); } printf("%llu\n",ans); printf("-----------\n");*/ } return 0; }
UVA 1363 Joseph's Problem 找规律+推导 给定n,k;求k%[1,n]的和。
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。