2019寒假培训第一天

时间:2022-05-08 09:45:10

B - Reversing Encryption

A string s of length n

can be encrypted by the following algorithm:

  • iterate over all divisors of n

in decreasing order (i.e. from n to 1

  • ),
  • for each divisor d
, reverse the substring s[1d] (i.e. the substring which starts at position 1 and ends at position d
  • ).

For example, the above algorithm applied to the string s

="codeforces" leads to the following changes: "codeforces" "secrofedoc" "orcesfedoc" "rocesfedoc" "rocesfedoc" (obviously, the last reverse operation doesn't change the string because d=1

).

You are given the encrypted string t

. Your task is to decrypt this string, i.e., to find a string s such that the above algorithm results in string t. It can be proven that this string s

always exists and is unique.

Input

The first line of input consists of a single integer n

(1n100) — the length of the string t. The second line of input consists of the string t. The length of t is n

, and it consists only of lowercase Latin letters.

Output

Print a string s

such that the above algorithm results in t

.

Examples
Input
10
rocesfedoc
Output
codeforces
Input
16
plmaetwoxesisiht
Output
thisisexampletwo
Input
1
z
Output
z
Note

The first example is described in the problem statement.

代码:
 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 string s;
 4 int a[101];
 5 int main()
 6 {
 7     int n;
 8    cin>>n;
 9    cin>>s;
10    int i=n;
11    int j=1;
12    a[0]=n;
13    for(int i=n-1;i>=2;i--)
14    {
15        if(n%i==0)
16         a[j++]=i;
17 
18    }
19    string s1;
20 for(int k=j;k>=0;k--)
21 {
22     s1=s.substr(0,a[k]);
23     reverse(s1.begin(),s1.end());
24     s.replace(0,a[k],s1);
25 }
26   cout<<s<<endl;
27  return 0;
28 }