最后一个：针对 n 范围比较大的解析
0、在公式：ans=(ans+m)%i 的基础上...当i很大，ans 和 m 都比较小的时候（i>>ans 和 m）。ans 每次增加的其实是 m。而这个增加次数可以算出来。所以...
1、当 ans + m >= i 时，普通递推。
2、当 ans + m < i 时，设增加次数为 x 次（代码中为：step 变量）。满足 ans + x * m < i + x - 1。
Ps：之所以是 x - 1，是因为 ans + m < i，ans + m + (x-1) * m < i + x -1。
3、由 2 得：x < (i - ans - 1) / (m - 1)；x = ceil((i - ans - 1) / (m - 1)) - 1。
4、由 3 得：ans += x * m，i += x。
5、但如果 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; }
