-
Notifications
You must be signed in to change notification settings - Fork 0
/
grooving_monkeys.cpp
118 lines (111 loc) · 4 KB
/
grooving_monkeys.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
/***
_________________________
| |
|_________________________|
| * * |
| *@IN* |
|___________*_*___________|
| |
|_________________________|
~@Scorpion
**/
#include<bits/stdc++.h>
#include<chrono>
#define BOOSTER ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define REPEAT intll t; cin >> t; for(intll iterator=0; iterator<t; iterator++)
#define isEven(e) ((e%2==0?true:false))
#define BLN 1000000000
#define MLN 1000000
#define LKH 100000
typedef long long intll;
typedef long intl;
using namespace std;
using namespace std::chrono;
template<typename E>
inline void write(const E &tar, string end="\n"){ cout << tar << end; }
template<typename E, typename L>
inline void write(const E *tar, const L len, string end=" "){ for(L i=0; i<len; i++) cout << tar[i] << end; }
template<typename E>
inline void write(const vector<E> &tar, intll len=INT64_MAX, string end=" "){len=min(len, (intll)tar.size());for(intll i=0; i<len; i++) cout << tar[i] << end;}
template<typename E>
inline void read(E &tar){ cin >> tar; }
template<typename E, typename L>
inline void read(E *tar, const L len){ for(L i=0; i<len; i++) cin >> tar[i]; }
template<typename E, typename L>
inline void read(vector<E> &tar, const L len){if(tar.size()>0) for(L i=0; i<tar.size(); i++) cin >> tar[i]; else for(L i=0; i<len; i++){ E temp; cin >> temp; tar.push_back(temp);}}
class File: public fstream{
public:
File(){}
File(string name):fstream(name){}
template<typename E>
inline void write(const E &tar, string end="\n"){ (*this)<< tar << end; }
template<typename E, typename L>
inline void write(const E *tar, const L len, string end=" "){ for(L i=0; i<len; i++) (*this) << tar[i] << end; }
template<typename E>
inline void write(const vector<E> &tar, string end=" "){ for(intll i=0; i<tar.size(); i++) (*this) << tar[i] << end; }
template<typename E>
inline void read(E &tar){ (*this) >> tar; }
template<typename E, typename L>
inline void read(E *tar, const L len){ for(L i=0; i<len; i++) (*this) >> tar[i]; }
template<typename E, typename L>
inline void read(vector<E> &tar, const L len){if(tar.size()>0) for(L i=0; i<tar.size(); i++) (*this) >> tar[i]; else for(L i=0; i<len; i++){ E temp; (*this) >> temp; tar.push_back(temp);}}
};
template<typename E>
E power(E val, intll expo){
E res = (E)1;
while(expo > 1LL){
if(expo % 2LL==0LL) val *= val, expo/=2LL;
else res *= val, --expo;
}
val *= res;
return val;
}
template<typename E>
E modPower(E val, intll expo, intll mod=BLN+7){
E res = (E)1;
while(expo > 0LL){
// odd
if(expo & 1LL) res = (res%mod) * (val%mod)%mod;
expo >>= 1LL;
val = (val%mod) * (val%mod) % mod;
}
return res%mod;
}
template<typename E>
void cookPrimes(vector<E> &primes, intll upto=MLN){
bool p[upto];
memset(p, false, sizeof(p));
for(intll i = 2 ;i*i <= upto ; i++){
intll m = i * i;
if(p[i] == false){
while( m <= upto){
p[m] = true;
m += i;
}
}
}
for(intll i = 2 ; i <= upto; i++) if(p[i] == false) primes.push_back(i);
}
int main(){
BOOSTER
REPEAT{
int n;
read(n);
int arr[n];
vector<intll> temp(n, 1);
read(arr, n);
int count, curr;
for(int i=0; i<n; i++){
// arr[i]--;
// count=0;
curr=i;
while(arr[curr]!=(i+1)) curr=arr[curr]-1, temp[i]++;
}
// write(temp);
// write("");
intll ans=1;
for(int i=0; i<n; i++) ans = ans * temp[i] / __gcd(ans, temp[i]);
write(ans);
}
return 0;
}