Circle

Time Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 320Accepted Submission(s): 102

Problem Description

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!

Input

The first line has a number T,means testcase number.

Each test,first line has a number n

The second line has n

numbers,which are the sequence in the Out Ordered**(The person who is out at ai

round was numbered i

)**.

The sequence input must be a permutation from 1

to n

.

1≤T≤10,2≤n≤20

Output

For each case,If there is a eligible number k

,output the smallest k

,otherwise,output”Creation August is a SB!”.

Sample Input

      
       1
7
7 6 5 4 3 2 1

Sample Output

Source BestCoder Round #80

考虑对给定的出圈序列进行一次模拟,对于出圈的人我们显然可以由位置,编号等关系得到一个同余方程一圈做下来我们就得到了n个同余方程对每个方程用扩展欧几里得求解,最后找到最小可行解就是答案. 当然不要忘了判无解的情况.

#include 
        
         
#include 
         
           #include 
          
            #include 
           
             #include 
            
              #include 
             
               #include 
              
                #include 
               
                 #include 
                 #include 
                 
                   #include 
                  
                    using namespace std; const int MAXN = 107; int num[MAXN]; long long mod[MAXN],b[MAXN]; // k(%mod)==b bool vis[MAXN]; void egcd(long long a, long long b, long long &d, long long &x, long long &y) { if (!b)d=a,x=1,y=0; else { egcd(b, a%b, d, y, x); y -= x*(a / b); } } long long CRT(int n) { long long M=mod[1],B=b[1],x,y,d; for (int i=2; i<=n; i++) { egcd(M,mod[i],d,x,y); if ((b[i]-B)%d)return -1; x=(b[i]-B)/d*x%(mod[i]/d); B+=x*M; M=M/d*mod[i]; B%=M; } return (B+M)%M(B+M)%M:M; } int main() { int T; cin>>T; while(T--) { int n,p; memset(vis,0,sizeof(vis)); scanf("%d",&n); for(int i=1; i<=n; ++i) { scanf("%d",&p); num[p]=i; } int j=1,k; for(int i=1; i<=n; ++i) { k=1; while(j!=num[i]) { if(!vis[j])++k; j=j%n+1; } vis[num[i]]=1; mod[i]=n-i+1; b[i]=k%mod[i]; } int flag=CRT(n); if(flag==-1)cout<<"Creation August is a SB!\n"; else cout<


【大中小】【打印】【繁体】【投稿】【收藏】【推荐】【举报】【评论】【关闭】【返回顶部】

上一篇：汇编语言学习第九章-转移指令的原..	下一篇：Hdu 5586 sum【最大连续子序列和】