给一个数字 $n$，要求你重排一个 $1\sim n$ 的排列 $a$，使得 $\sum\limits_{i=1}^{n-1}\gcd(a_i,a_{i+1})-\operatorname{lcm}(a_i,a_{i+1})$ 最大。请输出该值。

先打表找规律。这是程序：

#include<bits/stdc++.h>
using namespace std;
int n;
int a[100];
vector<int> res;
int ans;
int chk(){
  int r1=0,r2=0,i;
  for(i=0;i<n-3;i+=2){
    r1+=__gcd(a[i],a[i+1]),r2+=a[i]*a[i+1]/__gcd(a[i],a[i+1]);
    if(r1-r2<ans) return -0x3f3f3f3f;
    r1+=__gcd(a[i+1],a[i+2]),r2+=a[i+1]*a[i+2]/__gcd(a[i+1],a[i+2]);
    if(r1-r2<ans) return -0x3f3f3f3f;
  }
  for(;i<n-1;++i){
    r1+=__gcd(a[i],a[i+1]),r2+=a[i]*a[i+1]/__gcd(a[i],a[i+1]);
  }
  return r1-r2; 
}
int prime(int x){
  for(int i=2;i*i<=x;++i)
    if(x%i==0) return 0;
  return 1;
}
main(){
  for(n=1;n<=13;++n){
  for(int i=0;i<n;++i) a[i]=i+1;
  ans=-0x3f3f3f3f;
  do {
    if(a[0]%2==0&&a[n-1]%2==0) continue;
    if(!prime(a[0])) continue;
    if(n>10) for(int i=0;i<n-1;++i) if(abs(a[i]-a[i+1])==1) continue;
    int r=chk();
    if(r>ans){
      ans=r;
      res.clear();
      for(int i=0;i<n;++i) res.push_back(a[i]);
    }
    else if(r==ans) {
      for(int i=0;i<n;++i) res.push_back(a[i]);
    }
  } while(next_permutation(a,a+n));
  cout<<n<<": "<<ans<<'\n';
  int cc=0;
  for(int x:res) ++cc,cout<<x<<" \n"[cc%n==0]; 
  }
}

这是输出：

1: 0
1
2: -1
1 2
2 1
3: -3
2 1 3
3 1 2
4: -5
3 1 2 4
5: -13
5 1 3 2 4
6: -15
5 1 3 6 2 4
7: -32
5 2 4 6 3 1 7
5 3 6 2 4 1 7
7 1 3 6 4 2 5
7 1 4 2 6 3 5
8: -37
7 1 5 3 6 2 4 8
9: -48
7 1 5 2 8 4 6 3 9
10: -52
7 1 5 10 2 8 4 6 3 9
11: -88
7 3 9 6 4 8 2 10 5 1 11
11 1 5 10 2 8 4 6 9 3 7
12: -92
7 3 9 6 12 4 8 2 10 5 1 11
11 1 5 10 2 8 4 12 6 9 3 7
13: -142
11 2 5 10 4 8 12 6 9 3 7 1 13
11 2 10 5 4 8 12 6 9 3 7 1 13
11 3 9 6 12 4 8 2 10 5 7 1 13
13 1 7 3 9 6 12 8 4 5 10 2 11
13 1 7 3 9 6 12 8 4 10 5 2 11
13 1 7 5 10 2 8 4 12 6 9 3 11
//14 打不出来le

观察到首尾项离 $n$ 比较近。且 $n$ 为质数时降低幅度很大。有些项仅仅将 $n$ 插入之前的序列里。不知道还有没有其他规律求助QwQ