Harmonic Value Description
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 287 Accepted Submission(s): 184
Special Judge
Problem Description
The harmonic value of the permutation p1,p2,⋯pn is
∑i=1n−1gcd(pi.pi+1)
Mr. Frog is wondering about the permutation whose harmonic value is the strictly k-th smallest among all the permutations of [n].
Input
The first line contains only one integer T (1≤T≤100), which indicates the number of test cases.
For each test case, there is only one line describing the given integers n and k (1≤2k≤n≤10000).
Output
For each test case, output one line “Case #x: p1 p2 ⋯ pn”, where x is the case number (starting from 1) and p1 p2 ⋯ pn is the answer.
Sample Input
2
4 1
4 2
Sample Output
Case #1: 4 1 3 2
Case #2: 2 4 1 3
Source
求gcd值第k小的1到n的排列。
//2016.10.08
#include <iostream>
#include <cstdio>
#include <cstring> using namespace std; int main()
{
int T, n, k, kase = ;
scanf("%d", &T);
while(T--)
{
int tmp = -;
scanf("%d%d", &n, &k);
printf("Case #%d:", ++kase);
if(k == ){
for(int i = ; i <= n; i++)
printf(" %d", i);
}else{
if(k&){
printf(" %d %d", *k, k);
for(int i = ; i <= n; i++)
{
if(i == *k)continue;
if(i == k)printf("");
else printf(" %d", i);
}
}else{
printf(" %d %d", *k, k);
for(int i = ; i <= n; i++)
{
if(i == k || i == *k)continue;
else printf(" %d", i);
}
}
}
printf("\n");
} return ;
}