牛客多校(2020第五场) E Bogo Sort

题目链接: https://ac.nowcoder.com/acm/contest/5670/E

题意:给出一个置换P,问1~n这n个数有多少种排列,能经过若干次p的置换变为有序序列?答案对10^N取模

题解:找出数组中,每一个环得长度,求所有环的长度的最小公倍数

难点:大数模板,取环长度

计算环长度模板

 

牛客多校(2020第五场) E 	Bogo Sort
 1 for(int i=1; i<=n; i++)
 2 {
 3     if(!vis[i])
 4     {
 5         num.clear();
 6         int tmp=i;
 7         while(!vis[tmp])
 8         {
 9             vis[tmp]=1;
10             num.push_back(tmp);
11             tmp=a[tmp];
12         }
13         f();
14     }
15 }
View Code

 

大数模板

牛客多校(2020第五场) E 	Bogo Sort
  1 #define MAXN 9999
  2 #define MAXSIZE 500   //最大长度
  3 #define DLEN 4
  4 class BigNum {
  5 private:
  6     int a[21000];    //控制大数的位数
  7     int len;       //长度
  8 public:
  9     BigNum() { len = 1; memset(a, 0, sizeof(a)); }   //构造函数
 10     void XD();
 11     BigNum(const int);
 12     BigNum(const long long int);
 13     BigNum(const char*);
 14     BigNum(const string&);
 15     BigNum(const BigNum&);  //拷贝构造函数
 16     BigNum& operator = (const BigNum&);   //重载赋值运算符
 17     BigNum& operator = (const int&);
 18     BigNum& operator = (const long long int&);
 19  
 20     friend istream& operator >> (istream&, BigNum&);   //重载输入运算符
 21     friend ostream& operator << (ostream&, BigNum&);   //重载输出运算符
 22  
 23     template<typename T> BigNum operator << (const T&) const;
 24     template<typename T> BigNum operator >> (const T&) const;
 25  
 26     BigNum operator + (const BigNum&) const;   //重载加法运算符,大数加大数
 27     BigNum operator - (const BigNum&) const;   //重载减法运算符,大数减大数
 28     BigNum operator * (const BigNum&) const;   //重载乘法运算符,大数乘大数
 29     bool   operator > (const BigNum& b)const;   //重载大于
 30     bool   operator < (const BigNum& b) const;   //重载小于
 31     bool   operator == (const BigNum& b) const;  //重载等于符号
 32     template<typename T> BigNum operator / (const T&) const;    //重载除法运算符,大数除整数
 33     template<typename T> BigNum operator ^ (const T&) const;    //大数的n次方
 34     template<typename T> T    operator % (const T&) const;    //大数对int取模
 35  
 36     template<typename T> BigNum operator + (const T& b) const { BigNum t = b; t = *this + t; return t; }
 37     template<typename T> BigNum operator - (const T& b) const { BigNum t = b; t = *this - t; return t; }
 38     template<typename T> BigNum operator * (const T& b) const { BigNum t = b; t = (*this) * t; return t; }
 39     template<typename T> bool   operator < (const T& b) const { BigNum t = b; return ((*this) < t); }
 40     template<typename T> bool   operator > (const T& b) const { BigNum t = b; return ((*this) > t); }
 41     template<typename T> bool   operator == (const T& b) const { BigNum t = b; return ((*this) == t); }
 42  
 43     bool   operator <= (const BigNum& b) const { return (*this) < b || (*this) == b; }
 44     bool   operator >= (const BigNum& b) const { return (*this) > b || (*this) == b; }
 45     bool   operator != (const BigNum& b) const { return !((*this) == b); }
 46  
 47     template<typename T> bool   operator >= (const T& b) const { BigNum t = b; return !((*this) < t); }
 48     template<typename T> bool   operator <= (const T& b) const { BigNum t = b; return !((*this) > t); }
 49     template<typename T> bool   operator != (const T& b) const { BigNum t = b; return !((*this) == t); }
 50  
 51     BigNum& operator += (const BigNum& b) { *this = *this + b; return *this; }
 52     BigNum& operator -= (const BigNum& b) { *this = *this - b; return *this; }
 53     BigNum& operator *= (const BigNum& b) { *this = *this * b; return *this; }
 54     template<typename T> BigNum& operator /= (const T& b) { *this = *this / b; return *this; }
 55     template<typename T> BigNum& operator %= (const T& b) { *this = *this % b; return *this; }
 56     template<typename T> BigNum& operator += (const T& b) { *this = *this + b; return *this; }
 57     template<typename T> BigNum& operator -= (const T& b) { *this = *this - b; return *this; }
 58     template<typename T> BigNum& operator *= (const T& b) { *this = *this * b; return *this; }
 59     template<typename T> BigNum& operator ^= (const T& b) { *this = *this ^ b; return *this; }
 60  
 61     BigNum operator ++ (int) { BigNum t = *this; *this += 1; return t; }
 62     BigNum operator -- (int) { BigNum t = *this; *this -= 1; return t; }
 63     BigNum& operator -- () { *this -= 1; return *this; }
 64     BigNum& operator ++ () { *this += 1; return *this; }
 65  
 66     template<typename T> BigNum& operator <<= (const T& b) { *this = *this << b; return *this; }
 67     template<typename T> BigNum& operator >>= (const T& b) { *this = *this >> b; return *this; }
 68  
 69     template<typename T> BigNum friend operator + (const T& a, const BigNum& b) { BigNum t = a; t = t + a; return t; }
 70     template<typename T> BigNum friend operator - (const T& a, const BigNum& b) { BigNum t = a; t = t - b; return t; }
 71     template<typename T> BigNum friend operator * (const T& a, const BigNum& b) { BigNum t = a; t = t * b; return t; }
 72     template<typename T> friend bool operator < (const T& a, const BigNum& b) { return b > a; }
 73     template<typename T> friend bool operator > (const T& a, const BigNum& b) { return b < a; }
 74     template<typename T> friend bool operator <= (const T& a, const BigNum& b) { return b >= a; }
 75     template<typename T> friend bool operator >= (const T& a, const BigNum& b) { return b <= a; }
 76     template<typename T> friend bool operator == (const T& a, const BigNum& b) { return b == a; }
 77     template<typename T> friend bool operator != (const T& a, const BigNum& b) { return b != a; }
 78  
 79     void print();       //输出大数
 80     int Size();            //返回大数长度
 81     int the_first();    //返回第一个数字
 82     int the_last();        //返回最后一位数字
 83     int to_int();       //转化为整数
 84     long long int to_long();
 85     string to_String();        //转化为string类型
 86     //char* to_char();
 87 };
 88  
 89 BigNum::BigNum(const int b)     //将一个int类型的变量转化为大数
 90 {
 91     int c, d = b;
 92     len = 0;
 93     memset(a, 0, sizeof(a));
 94     while (d > MAXN) {
 95         c = d - (d / (MAXN + 1)) * (MAXN + 1);
 96         d = d / (MAXN + 1);
 97         a[len++] = c;
 98     }
 99     a[len++] = d;
100 }
101 BigNum::BigNum(const long long int b)
102 {
103     long long int c, d = b;
104     len = 0;
105     memset(a, 0, sizeof(a));
106     while (d > MAXN) {
107         c = d - (d / (MAXN + 1)) * (MAXN + 1);
108         d = d / (MAXN + 1);
109         a[len++] = c;
110     }
111     a[len++] = d;
112 }
113 BigNum::BigNum(const string& s)
114 {
115     int t, k, index, l, i;
116     memset(a, 0, sizeof(a));
117     l = s.size();
118     len = l / DLEN;
119     if (l % DLEN)
120         len++;
121     index = 0;
122     for (i = l - 1; i >= 0; i -= DLEN) {
123         t = 0;
124         k = i - DLEN + 1;
125         if (k < 0) k = 0;
126         for (int j = k; j <= i; j++)
127             t = t * 10 + s[j] - '0';
128         a[index++] = t;
129     }
130 }
131 BigNum::BigNum(const char* s)     //将一个字符串类型的变量转化为大数
132 {
133     int t, k, index, l, i;
134     memset(a, 0, sizeof(a));
135     l = strlen(s);
136     len = l / DLEN;
137     if (l % DLEN)
138         len++;
139     index = 0;
140     for (i = l - 1; i >= 0; i -= DLEN) {
141         t = 0;
142         k = i - DLEN + 1;
143         if (k < 0) k = 0;
144         for (int j = k; j <= i; j++)
145             t = t * 10 + s[j] - '0';
146         a[index++] = t;
147     }
148 }
149 BigNum::BigNum(const BigNum& b) : len(b.len)  //拷贝构造函数
150 {
151     memset(a, 0, sizeof(a));
152     for (int i = 0; i < len; i++)
153         a[i] = b.a[i];
154 }
155 BigNum& BigNum::operator = (const BigNum& n)   //重载赋值运算符,大数之间进行赋值运算
156 {
157     len = n.len;
158     memset(a, 0, sizeof(a));
159     for (int i = 0; i < len; i++)
160         a[i] = n.a[i];
161     return *this;
162 }
163 BigNum& BigNum::operator = (const int& num)
164 {
165     BigNum t(num);
166     *this = t;
167     return *this;
168 }
169 BigNum& BigNum::operator = (const long long int& num)
170 {
171     BigNum t(num);
172     *this = t;
173     return *this;
174 }
175 void XD()
176 {
177     cout << "A hidden egg! Good luck for u!" << endl;
178 }
179  
180 template<typename T> BigNum BigNum::operator << (const T& b) const
181 {
182     T temp = 1;
183     for (int i = 0; i < b; i++)
184         temp *= 2;
185     BigNum t = (*this) * temp;
186     return t;
187 }
188 template<typename T> BigNum BigNum::operator >> (const T& b) const
189 {
190     T temp = 1;
191     for (int i = 0; i < b; i++)
192         temp *= 2;
193     BigNum t = (*this) / temp;
194     return t;
195 }
196  
197 BigNum BigNum::operator + (const BigNum& b) const   //两个大数之间的相加运算
198 {
199     BigNum t(*this);
200     int i, big;
201     big = b.len > len ? b.len : len;
202     for (i = 0; i < big; i++) {
203         t.a[i] += b.a[i];
204         if (t.a[i] > MAXN) {
205             t.a[i + 1]++;
206             t.a[i] -= MAXN + 1;
207         }
208     }
209     if (t.a[big] != 0)
210         t.len = big + 1;
211     else
212         t.len = big;
213     return t;
214 }
215 BigNum BigNum::operator - (const BigNum& b) const   //两个大数之间的相减运算
216 {
217     int i, j, big;
218     bool flag;
219     BigNum t1, t2;
220     if (*this > b) {
221         t1 = *this;
222         t2 = b;
223         flag = 0;
224     }
225     else {
226         t1 = b;
227         t2 = *this;
228         flag = 1;
229     }
230     big = t1.len;
231     for (i = 0; i < big; i++) {
232         if (t1.a[i] < t2.a[i]) {
233             j = i + 1;
234             while (t1.a[j] == 0)
235                 j++;
236             t1.a[j--]--;
237             while (j > i)
238                 t1.a[j--] += MAXN;
239             t1.a[i] += MAXN + 1 - t2.a[i];
240         }
241         else
242             t1.a[i] -= t2.a[i];
243     }
244     t1.len = big;
245     while (t1.a[t1.len - 1] == 0 && t1.len > 1) {
246         t1.len--;
247         big--;
248     }
249     if (flag)
250         t1.a[big - 1] = 0 - t1.a[big - 1];
251     return t1;
252 }
253  
254 BigNum BigNum::operator * (const BigNum& b) const   //两个大数之间的相乘运算
255 {
256     BigNum ret;
257     int i, j, up;
258     int temp, temp1;
259     for (i = 0; i < len; i++) {
260         up = 0;
261         for (j = 0; j < b.len; j++) {
262             temp = a[i] * b.a[j] + ret.a[i + j] + up;
263             if (temp > MAXN) {
264                 temp1 = temp - temp / (MAXN + 1) * (MAXN + 1);
265                 up = temp / (MAXN + 1);
266                 ret.a[i + j] = temp1;
267             }
268             else {
269                 up = 0;
270                 ret.a[i + j] = temp;
271             }
272         }
273         if (up != 0) ret.a[i + j] = up;
274     }
275     ret.len = i + j;
276     while (ret.a[ret.len - 1] == 0 && ret.len > 1)
277         ret.len--;
278     return ret;
279 }
280 template<typename T> BigNum BigNum::operator / (const T& b) const
281 {
282     BigNum ret;
283     T i, down = 0;
284     for (i = len - 1; i >= 0; i--) {
285         ret.a[i] = (a[i] + down * (MAXN + 1)) / b;
286         down = a[i] + down * (MAXN + 1) - ret.a[i] * b;
287     }
288     ret.len = len;
289     while (ret.a[ret.len - 1] == 0 && ret.len > 1)
290         ret.len--;
291     return ret;
292 }
293 template<typename T> T BigNum::operator % (const T& b) const
294 {
295     T i, d = 0;
296     for (i = len - 1; i >= 0; i--) {
297         d = ((d * (MAXN + 1)) % b + a[i]) % b;
298     }
299     return d;
300 }
301  
302  
303 template<typename T> BigNum BigNum::operator^(const T& n) const    //大数的n次方运算
304 {
305     BigNum t, ret(1);
306     int i;
307     if (n < 0) return 0;
308     if (n == 0)
309         return 1;
310     if (n == 1)
311         return *this;
312     int m = n;
313     while (m > 1) {
314         t = *this;
315         for (i = 1; (i << 1) <= m; i <<= 1)
316             t = t * t;
317         m -= i;
318         ret = ret * t;
319         if (m == 1) ret = ret * (*this);
320     }
321     return ret;
322 }
323  
324 bool BigNum::operator > (const BigNum& b) const   //大数和另一个大数的大小比较
325 {
326     int tot;
327     if (len > b.len)
328         return true;
329     else if (len == b.len) {
330         tot = len - 1;
331         while (a[tot] == b.a[tot] && tot >= 0)
332             tot--;
333         if (tot >= 0 && a[tot] > b.a[tot])
334             return true;
335         else
336             return false;
337     }
338     else
339         return false;
340 }
341  
342 bool BigNum::operator < (const BigNum& b) const
343 {
344     int tot;
345     if (len > b.len)
346         return false;
347     else if (len == b.len) {
348         tot = len - 1;
349         while (a[tot] == b.a[tot] && tot >= 0)
350             tot--;
351         if (tot >= 0 && a[tot] > b.a[tot])
352             return false;
353         else
354             return false;
355     }
356     else
357         return true;
358 }
359  
360 bool BigNum::operator == (const BigNum& b) const
361 {
362     int tot = len - 1;
363     if (len != b.len)
364         return false;
365     while (a[tot] == b.a[tot] && tot >= 0)
366         tot--;
367     if (tot < 0)
368         return true;
369     return false;
370 }
371 int n;
372 void BigNum::print()    //输出大数
373 {
374     int i;
375     if (len >= n) {
376         cout << a[len - 1];
377         for (i = len - 2; i >= len - n; i--) {
378             cout.width(DLEN);
379             cout.fill('0');
380             cout << a[i];
381         }
382         cout << endl;
383     }
384     else {
385         cout << a[len - 1];
386         for (i = len - 2; i >= 0; i--) {
387             cout.width(DLEN);
388             cout.fill('0');
389             cout << a[i];
390         }
391         cout << endl;
392     }
393 }
394 int BigNum::Size()
395 {
396     int t = a[len - 1], cnt = 0;
397     while (t) { t /= 10; cnt++; }
398     cnt += (len - 1) * 4;
399     return cnt;
400 }
401 int BigNum::the_first()
402 {
403     int t = a[len - 1];
404     while (t > 10) { t /= 10; }
405     return t;
406 }
407 int BigNum::the_last()
408 {
409     int t = a[0];
410     return t % 10;
411 }
412 int BigNum::to_int()
413 {
414     int i, num;
415     num = a[len - 1];
416     for (i = len - 2; i >= 0; i--)
417         num = num * (MAXN + 1) + a[i];
418     return num;
419 }
420 long long int BigNum::to_long()
421 {
422     int i;
423     long long int num;
424     num = a[len - 1];
425     for (i = len - 2; i >= 0; i--)
426         num = num * (MAXN + 1) + a[i];
427     return num;
428 }
429 string BigNum::to_String()
430 {
431     int i;
432     string s = "", tp = "";
433     s += to_string(a[len - 1]);
434     for (i = len - 2; i >= 0; i--) {
435         tp = to_string(a[i]);
436         int tot = tp.size();
437         tp.insert(tp.begin(), 4 - tot, '0');
438         s = s + tp;
439     }
440     return s;
441 }
View Code

ac代码

牛客多校(2020第五场) E 	Bogo Sort
  1 #include<iostream>
  2 #include<cstring>
  3 #include<string>
  4 #include<cstdio>
  5 #include<algorithm>
  6 
  7 using namespace std;
  8 #define maxn 100100
  9 #define MAXN 9999
 10 #define MAXSIZE 500   //最大长度
 11 #define DLEN 4
 12 
 13 class BigNum {
 14 private:
 15     int a[21000];    //控制大数的位数
 16     int len;       //长度
 17 public:
 18     BigNum() { len = 1; memset(a, 0, sizeof(a)); }   //构造函数
 19     void XD();
 20     BigNum(const int);
 21     BigNum(const long long int);
 22     BigNum(const char*);
 23     BigNum(const string&);
 24     BigNum(const BigNum&);  //拷贝构造函数
 25     BigNum& operator = (const BigNum&);   //重载赋值运算符
 26     BigNum& operator = (const int&);
 27     BigNum& operator = (const long long int&);
 28  
 29     friend istream& operator >> (istream&, BigNum&);   //重载输入运算符
 30     friend ostream& operator << (ostream&, BigNum&);   //重载输出运算符
 31  
 32     template<typename T> BigNum operator << (const T&) const;
 33     template<typename T> BigNum operator >> (const T&) const;
 34  
 35     BigNum operator + (const BigNum&) const;   //重载加法运算符,大数加大数
 36     BigNum operator - (const BigNum&) const;   //重载减法运算符,大数减大数
 37     BigNum operator * (const BigNum&) const;   //重载乘法运算符,大数乘大数
 38     bool   operator > (const BigNum& b)const;   //重载大于
 39     bool   operator < (const BigNum& b) const;   //重载小于
 40     bool   operator == (const BigNum& b) const;  //重载等于符号
 41     template<typename T> BigNum operator / (const T&) const;    //重载除法运算符,大数除整数
 42     template<typename T> BigNum operator ^ (const T&) const;    //大数的n次方
 43     template<typename T> T    operator % (const T&) const;    //大数对int取模
 44  
 45     template<typename T> BigNum operator + (const T& b) const { BigNum t = b; t = *this + t; return t; }
 46     template<typename T> BigNum operator - (const T& b) const { BigNum t = b; t = *this - t; return t; }
 47     template<typename T> BigNum operator * (const T& b) const { BigNum t = b; t = (*this) * t; return t; }
 48     template<typename T> bool   operator < (const T& b) const { BigNum t = b; return ((*this) < t); }
 49     template<typename T> bool   operator > (const T& b) const { BigNum t = b; return ((*this) > t); }
 50     template<typename T> bool   operator == (const T& b) const { BigNum t = b; return ((*this) == t); }
 51  
 52     bool   operator <= (const BigNum& b) const { return (*this) < b || (*this) == b; }
 53     bool   operator >= (const BigNum& b) const { return (*this) > b || (*this) == b; }
 54     bool   operator != (const BigNum& b) const { return !((*this) == b); }
 55  
 56     template<typename T> bool   operator >= (const T& b) const { BigNum t = b; return !((*this) < t); }
 57     template<typename T> bool   operator <= (const T& b) const { BigNum t = b; return !((*this) > t); }
 58     template<typename T> bool   operator != (const T& b) const { BigNum t = b; return !((*this) == t); }
 59  
 60     BigNum& operator += (const BigNum& b) { *this = *this + b; return *this; }
 61     BigNum& operator -= (const BigNum& b) { *this = *this - b; return *this; }
 62     BigNum& operator *= (const BigNum& b) { *this = *this * b; return *this; }
 63     template<typename T> BigNum& operator /= (const T& b) { *this = *this / b; return *this; }
 64     template<typename T> BigNum& operator %= (const T& b) { *this = *this % b; return *this; }
 65     template<typename T> BigNum& operator += (const T& b) { *this = *this + b; return *this; }
 66     template<typename T> BigNum& operator -= (const T& b) { *this = *this - b; return *this; }
 67     template<typename T> BigNum& operator *= (const T& b) { *this = *this * b; return *this; }
 68     template<typename T> BigNum& operator ^= (const T& b) { *this = *this ^ b; return *this; }
 69  
 70     BigNum operator ++ (int) { BigNum t = *this; *this += 1; return t; }
 71     BigNum operator -- (int) { BigNum t = *this; *this -= 1; return t; }
 72     BigNum& operator -- () { *this -= 1; return *this; }
 73     BigNum& operator ++ () { *this += 1; return *this; }
 74  
 75     template<typename T> BigNum& operator <<= (const T& b) { *this = *this << b; return *this; }
 76     template<typename T> BigNum& operator >>= (const T& b) { *this = *this >> b; return *this; }
 77  
 78     template<typename T> BigNum friend operator + (const T& a, const BigNum& b) { BigNum t = a; t = t + a; return t; }
 79     template<typename T> BigNum friend operator - (const T& a, const BigNum& b) { BigNum t = a; t = t - b; return t; }
 80     template<typename T> BigNum friend operator * (const T& a, const BigNum& b) { BigNum t = a; t = t * b; return t; }
 81     template<typename T> friend bool operator < (const T& a, const BigNum& b) { return b > a; }
 82     template<typename T> friend bool operator > (const T& a, const BigNum& b) { return b < a; }
 83     template<typename T> friend bool operator <= (const T& a, const BigNum& b) { return b >= a; }
 84     template<typename T> friend bool operator >= (const T& a, const BigNum& b) { return b <= a; }
 85     template<typename T> friend bool operator == (const T& a, const BigNum& b) { return b == a; }
 86     template<typename T> friend bool operator != (const T& a, const BigNum& b) { return b != a; }
 87  
 88     void print();       //输出大数
 89     int Size();            //返回大数长度
 90     int the_first();    //返回第一个数字
 91     int the_last();        //返回最后一位数字
 92     int to_int();       //转化为整数
 93     long long int to_long();
 94     string to_String();        //转化为string类型
 95     //char* to_char();
 96 };
 97  
 98 BigNum::BigNum(const int b)     //将一个int类型的变量转化为大数
 99 {
100     int c, d = b;
101     len = 0;
102     memset(a, 0, sizeof(a));
103     while (d > MAXN) {
104         c = d - (d / (MAXN + 1)) * (MAXN + 1);
105         d = d / (MAXN + 1);
106         a[len++] = c;
107     }
108     a[len++] = d;
109 }
110 BigNum::BigNum(const long long int b)
111 {
112     long long int c, d = b;
113     len = 0;
114     memset(a, 0, sizeof(a));
115     while (d > MAXN) {
116         c = d - (d / (MAXN + 1)) * (MAXN + 1);
117         d = d / (MAXN + 1);
118         a[len++] = c;
119     }
120     a[len++] = d;
121 }
122 BigNum::BigNum(const string& s)
123 {
124     int t, k, index, l, i;
125     memset(a, 0, sizeof(a));
126     l = s.size();
127     len = l / DLEN;
128     if (l % DLEN)
129         len++;
130     index = 0;
131     for (i = l - 1; i >= 0; i -= DLEN) {
132         t = 0;
133         k = i - DLEN + 1;
134         if (k < 0) k = 0;
135         for (int j = k; j <= i; j++)
136             t = t * 10 + s[j] - '0';
137         a[index++] = t;
138     }
139 }
140 BigNum::BigNum(const char* s)     //将一个字符串类型的变量转化为大数
141 {
142     int t, k, index, l, i;
143     memset(a, 0, sizeof(a));
144     l = strlen(s);
145     len = l / DLEN;
146     if (l % DLEN)
147         len++;
148     index = 0;
149     for (i = l - 1; i >= 0; i -= DLEN) {
150         t = 0;
151         k = i - DLEN + 1;
152         if (k < 0) k = 0;
153         for (int j = k; j <= i; j++)
154             t = t * 10 + s[j] - '0';
155         a[index++] = t;
156     }
157 }
158 BigNum::BigNum(const BigNum& b) : len(b.len)  //拷贝构造函数
159 {
160     memset(a, 0, sizeof(a));
161     for (int i = 0; i < len; i++)
162         a[i] = b.a[i];
163 }
164 BigNum& BigNum::operator = (const BigNum& n)   //重载赋值运算符,大数之间进行赋值运算
165 {
166     len = n.len;
167     memset(a, 0, sizeof(a));
168     for (int i = 0; i < len; i++)
169         a[i] = n.a[i];
170     return *this;
171 }
172 BigNum& BigNum::operator = (const int& num)
173 {
174     BigNum t(num);
175     *this = t;
176     return *this;
177 }
178 BigNum& BigNum::operator = (const long long int& num)
179 {
180     BigNum t(num);
181     *this = t;
182     return *this;
183 }
184 void XD()
185 {
186     cout << "A hidden egg! Good luck for u!" << endl;
187 }
188  
189 template<typename T> BigNum BigNum::operator << (const T& b) const
190 {
191     T temp = 1;
192     for (int i = 0; i < b; i++)
193         temp *= 2;
194     BigNum t = (*this) * temp;
195     return t;
196 }
197 template<typename T> BigNum BigNum::operator >> (const T& b) const
198 {
199     T temp = 1;
200     for (int i = 0; i < b; i++)
201         temp *= 2;
202     BigNum t = (*this) / temp;
203     return t;
204 }
205  
206 BigNum BigNum::operator + (const BigNum& b) const   //两个大数之间的相加运算
207 {
208     BigNum t(*this);
209     int i, big;
210     big = b.len > len ? b.len : len;
211     for (i = 0; i < big; i++) {
212         t.a[i] += b.a[i];
213         if (t.a[i] > MAXN) {
214             t.a[i + 1]++;
215             t.a[i] -= MAXN + 1;
216         }
217     }
218     if (t.a[big] != 0)
219         t.len = big + 1;
220     else
221         t.len = big;
222     return t;
223 }
224 BigNum BigNum::operator - (const BigNum& b) const   //两个大数之间的相减运算
225 {
226     int i, j, big;
227     bool flag;
228     BigNum t1, t2;
229     if (*this > b) {
230         t1 = *this;
231         t2 = b;
232         flag = 0;
233     }
234     else {
235         t1 = b;
236         t2 = *this;
237         flag = 1;
238     }
239     big = t1.len;
240     for (i = 0; i < big; i++) {
241         if (t1.a[i] < t2.a[i]) {
242             j = i + 1;
243             while (t1.a[j] == 0)
244                 j++;
245             t1.a[j--]--;
246             while (j > i)
247                 t1.a[j--] += MAXN;
248             t1.a[i] += MAXN + 1 - t2.a[i];
249         }
250         else
251             t1.a[i] -= t2.a[i];
252     }
253     t1.len = big;
254     while (t1.a[t1.len - 1] == 0 && t1.len > 1) {
255         t1.len--;
256         big--;
257     }
258     if (flag)
259         t1.a[big - 1] = 0 - t1.a[big - 1];
260     return t1;
261 }
262  
263 BigNum BigNum::operator * (const BigNum& b) const   //两个大数之间的相乘运算
264 {
265     BigNum ret;
266     int i, j, up;
267     int temp, temp1;
268     for (i = 0; i < len; i++) {
269         up = 0;
270         for (j = 0; j < b.len; j++) {
271             temp = a[i] * b.a[j] + ret.a[i + j] + up;
272             if (temp > MAXN) {
273                 temp1 = temp - temp / (MAXN + 1) * (MAXN + 1);
274                 up = temp / (MAXN + 1);
275                 ret.a[i + j] = temp1;
276             }
277             else {
278                 up = 0;
279                 ret.a[i + j] = temp;
280             }
281         }
282         if (up != 0) ret.a[i + j] = up;
283     }
284     ret.len = i + j;
285     while (ret.a[ret.len - 1] == 0 && ret.len > 1)
286         ret.len--;
287     return ret;
288 }
289 template<typename T> BigNum BigNum::operator / (const T& b) const
290 {
291     BigNum ret;
292     T i, down = 0;
293     for (i = len - 1; i >= 0; i--) {
294         ret.a[i] = (a[i] + down * (MAXN + 1)) / b;
295         down = a[i] + down * (MAXN + 1) - ret.a[i] * b;
296     }
297     ret.len = len;
298     while (ret.a[ret.len - 1] == 0 && ret.len > 1)
299         ret.len--;
300     return ret;
301 }
302 template<typename T> T BigNum::operator % (const T& b) const
303 {
304     T i, d = 0;
305     for (i = len - 1; i >= 0; i--) {
306         d = ((d * (MAXN + 1)) % b + a[i]) % b;
307     }
308     return d;
309 }
310  
311  
312 template<typename T> BigNum BigNum::operator^(const T& n) const    //大数的n次方运算
313 {
314     BigNum t, ret(1);
315     int i;
316     if (n < 0) return 0;
317     if (n == 0)
318         return 1;
319     if (n == 1)
320         return *this;
321     int m = n;
322     while (m > 1) {
323         t = *this;
324         for (i = 1; (i << 1) <= m; i <<= 1)
325             t = t * t;
326         m -= i;
327         ret = ret * t;
328         if (m == 1) ret = ret * (*this);
329     }
330     return ret;
331 }
332  
333 bool BigNum::operator > (const BigNum& b) const   //大数和另一个大数的大小比较
334 {
335     int tot;
336     if (len > b.len)
337         return true;
338     else if (len == b.len) {
339         tot = len - 1;
340         while (a[tot] == b.a[tot] && tot >= 0)
341             tot--;
342         if (tot >= 0 && a[tot] > b.a[tot])
343             return true;
344         else
345             return false;
346     }
347     else
348         return false;
349 }
350  
351 bool BigNum::operator < (const BigNum& b) const
352 {
353     int tot;
354     if (len > b.len)
355         return false;
356     else if (len == b.len) {
357         tot = len - 1;
358         while (a[tot] == b.a[tot] && tot >= 0)
359             tot--;
360         if (tot >= 0 && a[tot] > b.a[tot])
361             return false;
362         else
363             return false;
364     }
365     else
366         return true;
367 }
368  
369 bool BigNum::operator == (const BigNum& b) const
370 {
371     int tot = len - 1;
372     if (len != b.len)
373         return false;
374     while (a[tot] == b.a[tot] && tot >= 0)
375         tot--;
376     if (tot < 0)
377         return true;
378     return false;
379 }
380 
381 int n; //定义n
382 
383 void BigNum::print()    //输出大数
384 {
385     int i;
386     if (len >= n) {
387         cout << a[len - 1];
388         for (i = len - 2; i >= len - n; i--) {
389             cout.width(DLEN);
390             cout.fill('0');
391             cout << a[i];
392         }
393         cout << endl;
394     }
395     else {
396         cout << a[len - 1];
397         for (i = len - 2; i >= 0; i--) {
398             cout.width(DLEN);
399             cout.fill('0');
400             cout << a[i];
401         }
402         cout << endl;
403     }
404 }
405 int BigNum::Size()
406 {
407     int t = a[len - 1], cnt = 0;
408     while (t) { t /= 10; cnt++; }
409     cnt += (len - 1) * 4;
410     return cnt;
411 }
412 int BigNum::the_first()
413 {
414     int t = a[len - 1];
415     while (t > 10) { t /= 10; }
416     return t;
417 }
418 int BigNum::the_last()
419 {
420     int t = a[0];
421     return t % 10;
422 }
423 int BigNum::to_int()
424 {
425     int i, num;
426     num = a[len - 1];
427     for (i = len - 2; i >= 0; i--)
428         num = num * (MAXN + 1) + a[i];
429     return num;
430 }
431 long long int BigNum::to_long()
432 {
433     int i;
434     long long int num;
435     num = a[len - 1];
436     for (i = len - 2; i >= 0; i--)
437         num = num * (MAXN + 1) + a[i];
438     return num;
439 }
440 string BigNum::to_String()
441 {
442     int i;
443     string s = "", tp = "";
444     s += to_string(a[len - 1]);
445     for (i = len - 2; i >= 0; i--) {
446         tp = to_string(a[i]);
447         int tot = tp.size();
448         tp.insert(tp.begin(), 4 - tot, '0');
449         s = s + tp;
450     }
451     return s;
452 }
453 
454 int p[maxn];
455 int to[maxn];
456 int vis[maxn];
457 
458 int gcd1(int x, int y) {
459     return y ? gcd1(y, x % y) : x;
460 }
461 int gcd(BigNum x, int y) {
462     return gcd1(y, x % y);
463 }
464 
465 BigNum lcm(BigNum ans, int res) {
466     return ans / gcd(ans, res) * res;
467 }
468 
469 int main() {
470     cin >> n; 
471     for (int i = 1; i <= n; i++) {
472         scanf("%d", &p[i]);
473         to[i] = p[i];
474     }
475 
476     BigNum ans = BigNum(1);
477     for (int i = 1; i <= n; i++) { //找环的长度
478         if (vis[i]) continue;
479         int tmp = i;
480         int res = 0; //环的长度
481         while (to[tmp] != i) {
482             vis[tmp] = 1;
483             tmp = to[tmp];
484             res++;
485         }
486         res++;
487         ans = lcm(ans, res);
488     }
489     ans.print();
490     return 0;
491 } 
View Code

参考链接:https://www.cnblogs.com/kangkang-/p/13387908.html

 

上一篇:为什么除数很大时除法会更快


下一篇:【历史遗留】还有记录的:HDOJ-刷题.md