c662 - Hello Oscar
題目描述
題目要求找出一個加密序列的週期，也就是加密多少次後會回到原始明文。給定一個祕密鍵，以及明文，每次加密都是將明文中的每個字元根據祕密鍵的對應位置重新排列。題目保證存在一個最小的加密次數 oscar，使得加密 oscar 次後會回到原始明文。
解題思路
這題的核心是找出加密過程中的循環。每次加密都可以看作是對明文的一個置換。我們可以將每次加密看作一個圖的節點移動，節點代表明文中的每個字元，邊代表加密過程中的位置變化。由於明文長度等於祕密鍵長度，因此每次加密都是一個排列。最終，我們會回到原始狀態，這意味著存在一個循環。
程式碼中，a 陣列儲存了祕密鍵。程式碼模擬了加密過程，並計算了每次加密後的結果。關鍵在於找到循環的長度。程式碼通過遍歷祕密鍵，追蹤每個字元的位置，直到回到起始位置，並計算這個循環的長度。然後，使用最小公倍數 (LCM) 的概念來計算 oscar 值。由於程式碼中使用了 gcd 函數，可以推斷出程式碼是通過迭代計算每個元素的循環長度，然後計算所有循環長度的最小公倍數來得到 oscar 值。
複雜度分析
- 時間複雜度: O(n^2)，其中 n 是祕密鍵的長度。最壞情況下，需要遍歷所有可能的循環，並且每次循環都需要 O(n) 的時間。
- 空間複雜度: O(n)，主要用於儲存祕密鍵
a陣列。
程式碼
#include <iostream>
using namespace std;
long long a[1005],it,tmp,ac;
string s;
long long gcd(long long x,long long y){
if( y==0 )
return x;
return gcd( y, x%y );
}
int main(){
cin.tie(0); ios::sync_with_stdio(false);
while(getline(cin,s)){
s+=' ';
it=0;
tmp=0;
ac=0;
for(int i=0;i<s.length();++i){
if(s[i]==' '&&ac){
a[it++]=tmp;
tmp=0;
ac=0;
}
else if(s[i]>='0'&&s[i]<='9'){
tmp*=10;
tmp+=s[i]-'0';
ac=1;
}
}
long long ans=1;
for(int i=0;i<it;++i){
long long tmp=0,it2=i;
while(a[it2]!=-1){
int k=a[it2];
a[it2]=-1;
it2=k;
tmp++;
}
//cout << tmp << " ";
//cout << ans << " ";
//cout << gcd(ans,tmp) << "\n";
if(tmp)ans=ans*tmp/gcd(ans,tmp);
//cout << ans << " ";
}
cout << ans << "\n";
}
}