sdut2383Decode the Strings（循环节）

http://acm.sdut.edu.cn/sdutoj/problem.php?action=showproblem&problemid=2383

一下午卡死在这道题上了还错了那么多次郁闷

最后经cz提醒用求出的循环节对每个字母的循环节取余算每个位置该输出什么字母

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define LL long long   
 4 char str[100],ss[10][101];
 5 LL gcd(LL a, LL b)
 6 {
 7     return b==0?a:gcd(b,a%b);
 8 }
 9 int main()
10 {
11     int n,i,j,aa,k,a[100],h[100],x,g,b[100];
12     LL m,s2;
13     while(scanf("%d%lld", &n,&m)!=EOF)
14     {
15         if(n==0&&m==0)
16             break;
17         memset(h,0,sizeof(h));
18         for(i = 1; i <= n ; i++)
19             scanf("%d", &a[i]);
20         getchar();
21         gets(str);
22         g =0;
23         int num = 0;
24         s2 = 1;
25         for(i = 1; i <= n; i++)
26         {
27             if(!h[i])
28             {
29                 num = 0;
30                 x = i;
31                 b[0] = i;
32                 int kk = 0;
33                 while(1)
34                 {
35                     x = a[x];
36                     kk++;
37                     b[kk] = x;
38                     num++;
39                     if(x==i)
40                         break;
41                 }
42                 for(j = 0 ; j < kk ; j++)
43                     h[b[j]] = num;
44                 s2 = s2/gcd(num,s2)*num;
45             }
46         }
47         m = s2-m%s2;
48         if(m==0)
49         {
50             puts(str);
51             continue;
52         }
53         for(i = 1;i <= n; i++)
54         {
55             k = m%h[i];
56             aa = i;
57             for(j = 1; j <= k ; j++)
58             {
59                 aa = a[aa];
60             }
61             printf("%c",str[aa-1]);
62         }
63         puts("");
64     }
65     return 0;
66 }