hdu_5668 Circle

题目:

  Satiya August is in charge of souls.
  He finds n souls,and lets them become a circle.He ordered them to play Joseph Games.The souls will count off from the soul 1.The soul who is numbered k will be taken out,and will not join in the game again.
  Now Satiya August has got the sequence in the Out Ordered,and ask you the smallest k.If you cannot give him a correct answer,he will kill you!

思路:

  假设现在已经出去了个灵魂(从开始记),代表走到下一个出去的灵魂需要走几步,那么不难列出方程,用中国剩余定理求出方程组的解即可。
  因为数据很小,所以求的过程可以直接模拟。

代码:

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
#define lcm(a,b) ((a)/gcd(a,b)*(b))
void exgcd(ll a,ll b,ll &d,ll &x,ll &y){
    if(!b){d=a;x=1;y=0;return;}
    exgcd(b,a%b,d,y,x);y-=a/b*x;
}
ll calc(ll a,ll b,ll c){
    ll x,y,d;
    exgcd(a,b,d,x,y);
    if(c%d)return -1;
    a/=d;b/=d;c/=d;
    return (x*c%b+b)%b;
}
struct CRT{
    ll A,M;
    CRT(){A=0;M=1;}
    bool insert(ll a,ll m){
        ll k=calc(M,m,a-A);
        if(!~k)return false;
        A+=M*k;
        M=lcm(M,m);
        return true;
    }
};
int sol[25],n;
bool out[25];
void solve(){
    int t=0,p;
    CRT crt;
    memset(out,0,sizeof(out));
    for(int i=0;i<n;i++){
        for(p=1;t!=sol[i];t=(t+1)%n,p+=(!out[t]));
        t=(t+1)%n;
        out[t]=true;;
        if(!crt.insert(p,n-i)){
            puts("Creation August is a SB!");
            return;
        }
    }
    printf("%lld\n",crt.A?crt.A:crt.M);
}
int main(){
    int T;
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=0,x;i<n;i++){
            scanf("%d",&x);
            sol[x-1]=i;
        }
        solve();
    }
    return 0;
}