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
- ).
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).
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 salways exists and is unique.
InputThe first line of input consists of a single integer n
(1≤n≤100) — 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.
OutputPrint 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
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 }