UVA 12103 - Leonardo's Notebook(数论置换群)

本文主要是介绍UVA 12103 - Leonardo's Notebook(数论置换群)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

UVA 12103 - Leonardo's Notebook

题目链接

题意：给定一个字母置换B，求是否存在A使得A^2=B

思路：任意一个长为 L 的置换的k次幂，会把自己分裂成gcd(L,k) 分， 并且每一份的长度都为 L / gcd(l,k)，因此平方对于奇数长度不变，偶数则会分裂成两份长度相同的循环，因此如果B中偶数长度的循环个数不为偶数必然不存在A了

代码：

#include <stdio.h>
#include <string.h>const int N = 30;
int t, next[N], vis[N], num[N];
char str[N];bool judge() {for (int i = 2; i <= 26; i += 2)if (num[i] % 2) return false;return true;
}int main() {scanf("%d", &t);while (t--) {scanf("%s", str);for (int i = 0; i < 26; i++)next[i] = str[i] - 'A';memset(vis, 0, sizeof(vis));memset(num, 0, sizeof(num));for (int i = 0; i < 26; i++) {if (!vis[i]) {vis[i] = 1;int t = next[i];int cnt = 1;while (!vis[t]) {vis[t] = 1;t = next[t];cnt++;}num[cnt]++;}}printf("%s\n", judge()?"Yes":"No");}return 0;
}

这篇关于UVA 12103 - Leonardo's Notebook(数论置换群)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---