poj2800 Joseph's Problem

痛定思痛。 2023-07-04 14:19 2阅读 0赞

**Discription**  
Joseph likes taking part in programming contests. His favorite problem is, of course, Joseph’s problem.  
It is stated as follows.  
There are n persons numbered from 0 to n - 1 standing in a circle. The person number  
k, counting from the person number 0, is executed. After that the person number k of the  
remaining persons is executed, counting from the person after the last executed one. The  
process continues until only one person is left. This person is a survivor. The problem is,  
given n and k detect the survivor’s number in the original circle.  
Of course, all of you know the way to solve this problem. The solution is very short, all you need  
is one cycle:  
r := 0;  
for i from 1 to n do  
r := (r + k) mod i;  
return r;  
Here “x mod y” is the remainder of the division of x by y  
But Joseph is not very smart. He learned the algorithm, but did not learn the reasoning behind it.  
Thus he has forgotten the details of the algorithm and remembers the solution just approximately.  
He told his friend Andrew about the problem, but claimed that the solution can be found using the  
following algorithm:  
r := 0;  
for i from 1 to n do  
r := r + (k mod i);  
return r;  
Of course, Andrew pointed out that Joseph was wrong. But calculating the function Joseph described is also very interesting.  
Given n and k, find ∑ni=1(k mod i).

**Input**  
The input file contains several test cases, each of them consists of a line containing n and k (1 ≤ n, k ≤109)

**Output**  
For each test case, output a line containing the sum requested.

**Sample Input**  
5 3

**Sample Input**  
7

**题意**  
求∑1<=i<=n(k mod i)的值

**思路**  
有三种情况：  
1、1<k<n；  
2、k == n ;  
3、k>n;  
当k到n时： sum =(n-k)*k;  
当1到a时： for( i = 1 , sum = 0 ; i <= k ; i ++ ) sum += k %i ;  
但是这样容易超时，  
所以将问题分解：  
1到k/2： for( i = k/2 ; i >=1 ; i-- ) sum+= k % i ;  
k/2到k：k%k+((k-1)+1)%(k-1)+…+ (k-m0)+m0)%(k-m0) 其中m0 < k –m0 , 则m0<k/2, 又因为m0 是整数所以m0 = k/2 – 1 ;  
如果k%i ( i ++ ) 只要 k/i (i ++ ) 的值相同 ， 则 k % i 是以个等差数列.  
继续优化得到：  
(k%(k/1)+k%(k/2+1))*(k/1-k/2)/2+(k%(k/2)+k%(k/3+1))*(k/2-k/3)/2+…设s=k/i;e=k/(i-1);  
则上诉式子就变为： sum+=(k%e+k%(s+1))*(e-s)/2;  
时间复杂度仅为sqrt(k);

所以就是把sum分为三部分：  
1、 sum+=(k%e+k%(s+1))\*(e-s)/2  
2、for(i=1;i<=n&&i<=b;i++) sum+=k%i; 其中b = k / sqrt(k) ;  
3、 sum += (n-k)\*k ;

**AC代码**

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    ll n,k,ans;
    int main()
    { 
        while(~scanf("%lld %lld",&n,&k))
        { 
            ans=0;
            if(n>k)
                ans+=(n-k)*k;
            for(ll i=(ll)sqrt(k); i>1; i--)
            { 
                ll l=k/i;
                ll r=k/(i-1);
                if(l>n)
                    break;
                if(r>n)
                    r=n;
                ans+=(k%r+k%(l+1))*(r-l)/2;
            }
            for(ll i=1; i<=n&&i<=k/(ll)sqrt(k); i++)
                ans+=k%i;
            printf("%lld\n",ans);
        }
        return 0;
    }