ACM-ICPC Shenyang Oniste 2018 K. Let the Flames Begin（約瑟夫環 + 分塊）

​​ACM-ICPC Shenyang Oniste 2018 K. Let the Flames Begin​​

題目

約瑟夫環編号 1 ~ n，問你第 m 個人死的編号。（每次數 k 個人），

1 <= n,m, k <= 1e18，（==m，k最小值小于 1e6）

分析

因為是約瑟夫環問題，複習下遞推公式。（約瑟夫環問題都是用公式考慮編号從零開始，如果不是，結果 + 1 即可）

假如有 0 到 n 一共 n+1 個點， 表示數到最後的編号，第一個出隊的是 ，考慮目前删一個點的狀況：相當于 n 個點的規模， 0 号點變為原來 k 号點，（即圖二的編号整體移動 k。）

公式表示為：

即：

分析要求第 m 個的編号，根據上面的遞推過程，有：

這樣就可以遞推求解，但是題目範圍 1e18，顯然不現實。但是題目還給出一個條件 m 和 k 一定有一個比較小，顯然要從這裡入手。

#include <bits/stdc++.h>
using namespace std;
#define INF 0x3f3f3f3f
#define ll long long
#define fuck(x) cout<<x<<endl
const int N = 1e3 + 10;
const int mod = 998244353;

ll t, n, m, k, ans;

int main(){
  int cas = 1;
  scanf("%lld\n", &t);
  while(t--){
    scanf("%lld%lld%lld", &n, &m, &k);
    printf("Case #%d: ", cas++);
    if(m < k){   //  m 比較小
      ans = (k - 1) % (n - m + 1);    // 遞歸改遞推
      for(ll i = n - m + 2; i <= n; i++){
        ans = (ans + k) % i;
      }
      printf("%lld\n", ans + 1);
    }else{
      if(k == 1){
        printf("%lld\n", m);
      }else{
        ans = (k - 1) % (n - m + 1);    // m = 1時， k - 1是第一個出去的
        for(ll i = n - m + 2, j = i; i <= n; i = j+1){
          ll tmp = (i - 1 - ans) / (k - 1); // 每次前進 k 個，就有 k-1 的間隔
          if((i - 1 - ans) % (k - 1) != 0){ // 不能整除的話，會多一
            tmp++;
          }
          if(i + tmp - 1 >= n){        // 如果大于 n ，證明剩下到 n 直接乘就行
            ans = (ans + (n - i + 1) * k) % n;
            break;
          }
          ans = (ans + tmp * k) % (i + tmp - 1);
          j = i + tmp - 1;
        }
        printf("%lld\n", ans + 1);
      }
    }
  }
}