题意:
给出m位的n进制数;
要求这个数字乘以2,3…m,都是本身数字的排列;
例如6位 ,十进制
2 x 142,857 = 285,714 3 x 142,857 = 428,571 4 x 142,857 = 571,428 5 x 142,857 = 714,285 6 x 142,857 = 857,142现在给出m(3 <= m <= 6) ,n;求这个数字;
思路:
我们可以得出一个规律;
如果是m位数;
那么我们就可以得到m个数字,就是所求的这个数字乘以1,2,3…m;
这m个数字中,每个数字的个位全都不一样,并且刚好是组成这个数字的那些数;
例如142857,得到的6个数字就是
142857
285714
428571
571428
714285
857142
这些数字个位数恰好就是这个数字的组成部分;
那么我们就可以枚举个位数,然后通过这个个位数,求出剩下的组成部分;
然后通过排列组合暴力求出这个个位数是否可行;
AC代码:
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;int num[7];int vis[7];int Sort[7];int n, m;bool solve(int x) {for(int i = 2; i <= m; i++) {Sort[i] = i;}do {bool flag2 = true;for(int i = 2 ;i <= m ;i++){memset(vis, 0 ,sizeof(vis));vis[i] = 1;int c = x * i / n;for(int j = 2 ; j <= m; j++) {int temp = (num[Sort[j]] * i + c)% n;c = (num[Sort[j]] * i + c) / n;bool flag = false;for(int k = 1; k <= m; k++) {if(temp == num[k] && !vis[k]) {vis[k] = 1;flag = true;break;}}if(!flag) {flag2 = false;break;}}if(!flag2) {break;}}if(flag2)return true;}while(next_permutation(Sort + 2 ,Sort + m + 1));return false;}int main() {while(scanf("%d%d",&m, &n) && m) {bool flag = false;for(int i = 1; i < n; i++) {for(int j = 1; j <= m; j++) {num[j] = (i * j) % n;}if(solve(i)) {flag = true;for(int j = m; j >= 2; j–) {printf("%d ",num[Sort[j]]);}printf("%d\n",i);break;}}if(!flag)printf("Not found.\n");}}
,有的旅行是为了体验生活,感悟人生。