hdu 3089 约瑟夫环

原来并不知道约瑟夫环还可以递推直接解orz

约瑟夫问题的递推公式：

设f[n]表示一共n个人，数到k出局，这样最后的winner (n个人从0开始标号，即0--n-1)

f[n]=(f[n-1]+k)%n　　　　（注意%n里这个n也是变量

初值f[1]=0

【公式的详细证明可以refer这里：http://blog.****.net/a725sasa/article/details/11664375 】

不过本题n很大，O(n)仍然会爆

注意到公式中的%n：如果f[n-1]+k小于n，那么就不用再mod了

如果f[n-1]+若干个k还是很小，就可以一次多跳几步

Reference：http://blog.****.net/gyarenas/article/details/9073045

 //f[1]=0    f[i]=(f[i-1]+m)%i
 //ty=(tx+m)%i
 #include<iostream>
 #include<cstdio>
 #include<cstring>
 using namespace std;
 #define LL long long
 LL n,k;

 LL solve(LL n,LL k)
 {
     LL i=;
     LL tx=;
     while(i<=n)
     {
         LL x=(i--tx)%(k-)?(i--tx)/(k-):(i--tx)/(k-)-;
         if(tx+k<i)
         {
             if(i+x>n)
             {
                 tx=tx+(n+-i)*k;
                 return(tx);
             }
             tx=tx+x*k;
             i+=x;
         }
         else
         {
             tx=(tx+k)%i;
             i++;
         }
     }
     return(tx);
 }

 int main()
 {
     while(scanf("%I64d%I64d",&n,&k)!=EOF)
     {
         int i=;
         LL tx=;
         if(k==)
         {
             tx=(n-)%n;
         }
         else
             tx=solve(n,k);
         tx=(tx+)%n;
         if(tx==)   tx+=n;
         printf("%I64d\n",tx);
     }
 }