题意:给定一个字母置换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(数论置换群),布布扣,bubuko.com
UVA 12103 - Leonardo's Notebook(数论置换群)
原文:http://blog.csdn.net/accelerator_/article/details/37927387