codeforces B. Levko and Permutation 解题报告

题目链接：http://codeforces.com/problemset/problem/361/B

题目意思：有n个数，这些数的范围是[1，n]，并且每个数都是不相同的。你需要构造一个排列，使得这个排列上的数与它所在位置的序号的最大公约数满足 > 1，并且这些数的个数恰好满足k个，输出这样的一个排列。

先说明什么时候得不到这样的一个排列，就是n = k的情况。因为任何一个数x放在第1个位置的gcd(x, 1) = 1的，所以要得出这样一个排列 k 最大只能为 n-1 。而k最小为0个，这个排列是n，2，3，4，...，n-1（当然也可以是2，3，...，n，n+1等等）。那么，如果k 满足 [0, n - 1]的取值范围，这样的排列绝对存在。

接着讨论一般情况下，如果构造出满足恰好有k个符合这样条件的排列。这里先声明一个规律，当某个数x放在与它下标也是x的位置上时（这个数当然不能为1），那么绝对是满足gcd(x, x) > 1的，最大公约数即是它自己。现在推出构造这个排列的规律。

假设n = 8， k = 2

下标i : 1 2 3 4 5　　 6 　　　 7 8

排列xi: 2 3　　 4 5 6 1 7 8

如果 k= 3

下标i : 1 2 3 4 5　　 6 　　　 7 8

排列xi： 2 3 4　　 5 1 6 7 8

其他依此类推，可以发现前n-k-1 个数都是从比它下标多1开始的，这样保证gcd(i, xi) = 1，而第n-k的位置填1，这样加起来恰好满足gcd(i, xi)的个数等于n-k，而最后的k个数则保持与它的下标相等。

 #include <iostream>

 #include <cstdio>

 #include <cstdlib>

 using namespace std;

 int main()

 {

     int i,  n, k;

     while (scanf("%d%d", &n, &k) != EOF)

     {

         if (k == )

         {

             printf("%d ", n);

             for (i = ; i < n; i++)

                 printf("%d ", i);

         }

         else if (k == n)

             printf("-1\n");

         else

         {

             for (i = ; i < n - k; i++)

                 printf("%d ", i+);

             printf("1 ");

             for (i = n-k+; i <= n; i++)

                 printf("%d ", i);

             printf("\n");

         }

     }

     return ;

 }

巴特西

codeforces B. Levko and Permutation 解题报告

最新文章

热门文章