Problem J. Joseph’s Problem 约瑟夫问题--余数之和

链接：https://vjudge.net/problem/UVA-1363

题意：给出n  k，当 i 属于 1~n 时 ，求解 n% i 的和

n 和 k 的范围都是 1 到 10^9;

商相同 的余数数列 是 公差为商 的 递减等差数列

应该让k / i相等的一连串k % i相加，举个例子：

100 / 34 = 2 ... 32

100 / 35 = 2 ... 30

100 / 36 = 2 ... 28

...

100 / 50 = 2 ... 0

递减等差数列通项公式：an=a1-(n-1)*d

前n项和公式：sum=n*a1-n*(n-1)*d/2;

#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
ll n,k,d,a,len,sum;
int main()
{
     freopen("joseph.in","r",stdin);
     freopen("joseph.out","w",stdout);
    while(cin>>n>>k)
    {
        sum=0;
        for(ll i=2;i<=n;i=i+len)
        {
            d=k/i;//公差
            a=k%i;//递减等差数列的首项，最长递减到零结束
            if(i>k)
            {
                sum=sum+k*(n-k);
                break;
            }
            len=a/d+1;//由递减等差数列的的通项公式an=a1+(n-1)*d解得数列递减到0的长度
            len=min(len,n-i+1);//最后一段等差数列可能没有递减到零，长度要另外判断
            sum=sum+len*a-len*(len-1)*d/2;//等差数列前n项和公式
        }
        cout<<sum<<endl;
    }
    return 0;
}