ACM模版——約瑟夫問題（出列順序 + 最後一個）

最後一個：針對 n 範圍比較大的解析c++

0、在公式：ans=(ans+m)%i 的基礎上...當i很大，ans 和 m 都比較小的時候（i>>ans 和 m）。ans 每次增長的實際上是 m。而這個增長次數能夠算出來。因此...數組

一、當 ans + m >= i 時，普通遞推。spa

二、當 ans + m < i 時，設增長次數爲 x 次（代碼中爲：step 變量）。知足 ans + x * m < i + x - 1。
code

Ps：之因此是 x - 1，是由於 ans + m < i，ans + m + (x-1) * m < i + x -1。it

三、由 2 得：x < (i - ans - 1) / (m - 1)；x = ceil((i - ans - 1) / (m - 1)) - 1。class

四、由 3 得：ans += x * m，i += x。基礎

五、但若是 i 增長的總次數 (i + x) > n 了，那麼最終結果應增長 (n - i + 1) * m 次，而不是 i+x 次。變量

#include<bits/stdc++.h>
#include<cmath>

#define mem(a,b) memset(a,b,sizeof a)
#define INF 0x3f3f3f3f

using namespace std;

typedef long long ll;

int main()
{
    ll n,m;
    while(~scanf("%lld%lld",&n,&m))
    {
        /* 最後一個：針對n範圍比較小的解決方案 */
        // 編號從0開始
//        int ans=0;
//        for(int i=2;i<=n;i++)
//            ans=(ans+m)%i;
//        printf("%d\n",ans); // 輸出的是數組下標

        /* 最後一個：針對n範圍比較大的解決方案 HDU3089 */
        // 編號從0開始
//        ll ans=0,step=0;
//        if(m==1) ans=n-1;
//        else if(n==1) ans=0;
//        else
//        {
//            for(ll i=2;i<=n;)
//            {
//                if(ans+m<i)
//                {
////                    step=(i-1-ans)%(m-1)?(i-1-ans)/(m-1):(i-1-ans)/(m-1)-1; // 等價下面這行代碼
//                    step=ceil((i-1-ans)*1.0/(m-1))-1;
//                    if(i+step>n)
//                    {
//                        ans+=(n-i+1)*m; // (n-i+1)次
//                        break;
//                    }
//
//                    ans+=step*m;
//                    i+=step;
//                }
//                else
//                    ans=(ans+m)%i++;
//            }
//            ans%=n;
//        }
//
//        printf("%lld\n",ans+1); // 輸出的是數組下標

        /* 出列順序：針對出列順序解決方案O(n*m) */
        // 編號從0開始
//        int idx=0,cnt=1,pout=0,vis[n+10];
//        mem(vis,0);
//        while(pout!=n) // out人數是否滿
//        {
//            if(1==vis[idx]) // 已out
//            {
//                idx=(idx+1)%n;
//                continue;
//            }
//
//            if(cnt%m==0) // 準備out
//            {
//                vis[idx]=1;
//                pout++;
//                printf("%d\n",idx+1);
//            }
//
//            idx=(idx+1)%n; // 繼續報數
//            cnt++;
//        }

        /* 針對出列順序解決方案O(n*(logn)^2) */
        // 待更新...
    }

    return 0;
}