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 = ;
sum = n*a1+n*(n-)/*d;
return sum;
}
int main()
{
int n, k;
while(scanf("%d%d",&n,&k)==)
{
ull a1, m, d;
ull ans = ;
for(int i = ; i <= n; i+=m){
a1 = k%i;
d = -k/i;
if(d==){
ans += (ull)(n-i+)*k;
break;
}
m = a1/(k/i)+;
m = min(m,ull(n-i+));///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 ;
}
上一篇:LA 3521 Joseph's Problem


下一篇:UVa 1363 (数论 数列求和) Joseph's Problem