ACM-ICPC 2018 沈阳赛区现场赛 K. Let the Flames Begin （约瑟夫环问题）

题目链接：

题意：有 n 个人围成一个圈，从 1 开始报到第 k 个人出环，问第 m 个出环的人是谁，n、m、k <= 1e18 且 min（m，k）<= 2e6。

题解：容易得出O（m）的递推公式 f[n][m] = （f[n-1][m-1] + k - 1）% n + 1，初始状态 f[n-m+1][1]容易得出，当 m 小的时候用该公式计算。考虑 k 大 m 小的情况下，递推式的取膜很多情况下没有用到，可以用乘法代替加法加速递推的过程：

当前状态为f[a][b] = c， 经过 x 次加法后的状态为 f[a+x][b+x] = c + k * x，假设经过 x 次加法之后需要取模，有

c + k * x > a + x   →   x > （a - c）/ （k - 1）

得到该不等式后便可以计算出另一种情况了，还要注意 k = 1 需要特判。

 #include <bits/stdc++.h>

 using namespace std;

 #define ll long long

 #define ull unsigned long long

 #define mst(a,b) memset((a),(b),sizeof(a))

 #define mp(a,b) make_pair(a,b)

 #define pi acos(-1)

 #define pii pair<int,int>

 #define pb push_back

 const int INF = 0x3f3f3f3f;

 const double eps = 1e-;

 const int MAXN = 2e6 + ;

 const int MAXM = 1e8 + ;

 const ll mod = 1e9 + ;

 ll f[MAXN];

 int main() {

 #ifdef local

     freopen("data.txt", "r", stdin);

 //    freopen("data.txt", "w", stdout);

 #endif

     int cas = ;

     int t;

     scanf("%d",&t);

     while(t--) {

         ll n,m,k;

         scanf("%lld%lld%lld",&n,&m,&k);

         printf("Case #%d: ",cas++);

         if(m <= k) {

             f[] = k % (n - m + );

             if(f[] == ) f[] = n - m + ;

             for(ll i = ; i <= m; i++)

                 f[i] = (f[i - ] + k - ) % (n - m + i) + ;

             printf("%lld\n",f[m]);

         } else {

             if(k == ) printf("%lld\n",m);

             else {

                 ll a = n - m + , b = ;

                 ll c = k % a, x = ;

                 if(c == ) c = a;

                 while(b + x <= m) {

                     a += x, b += x, c += k * x;

                     c %= a;

                     if(c == ) c = a;

                     x = (a - c) / (k - ) + ;

                 }

                 c += (m - b) * k;

                 c %= n;

                 if(c == ) c = n;

                 printf("%lld\n",c);

             }

         }

     }

     return ;

 }