Am I the last person who knows these things?

· · 算法·理论

Preamble

这里都是一些我意料之外的小知识点。

例题题单：https://www.luogu.com.cn/training/774416

Chapter 1

Part 1

以上图片（以及 OEIS A002182）流传极为广泛，常常在数论相关题目中用到。

然而，考场上拿不到这些资料，于是我们需要手推。

对于 \max\{\omega(n)\}，我们直接贪心（计算 2 \times 3 \times 5 \times 7 \times \ldots）即可计算（并找出最优解）。

对于 \max\{d(n)\}，我们设 n = p_1^{q_1} \times p_2^{q_2} \times p_3^{q_3} \times \ldots \times p_t^{q_t}，其中 q_1 \ge q_2 \ge q_3 \ge \ldots \ge q_t \ge 1，p_1,p_2,p_3,\ldots,p_t 均为质数。

显然，在 d(n) 不变的情况下，当 p_1,p_2,p_3,\ldots,p_t 依次取前 t 个质数时，n 的值最小。

根据这一原理，我们可以直接 DFS 搜索符合要求的 n，并借此找出 \max\{d(n)\} 和最优解。

#include <bits/stdc++.h>
#define int __int128
using namespace std;
const int prime[17]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
long long maxd=0;
long long maxn=1;
long long limit;
void dfs(int cur,int expo,int maxe,int frac,int num)
{
    if(num>limit) return;
    if(expo>maxe) return;
    if(frac>maxd) maxd=frac,maxn=num;
    if(frac==maxd&&num<maxn) maxn=num;
    dfs(cur,expo+1,maxe,frac/(expo+1)*(expo+2),num*prime[cur]);
    dfs(cur+1,1,expo,frac*2,num*prime[cur+1]);
}
signed main()
{
    cin>>limit;
    dfs(1,0,INT_MAX,1,1);
    cout<<maxd<<' '<<maxn<<endl;
    return 0;
}

在洛谷的评测机上，（微调后的）该代码在输入 10^{36} 后的运行用时仅有 52 \text{ ms}，并且输出：

127401984 812899257272051723607760622343648000

根据 Wolframalpha，这个数的质因数分解为：

2^8\times3^5\times5^3\times7^2\times11^2\times13\times17\times\ldots\times73

其因数个数为：

9\times6\times4\times3^2\times2^{16}=127401984

Part 2

在此基础上，我们对所有可能的输出进行整理，即可得到 OEIS A002182：

    d(n)                     n
       1                     1
       2                     2
       3                     4
       4                     6
       6                    12
       8                    24
       9                    36
      10                    48
      12                    60
      16                   120
      18                   180
      20                   240
      24                   360
      30                   720
      32                   840
      36                  1260
      40                  1680
      48                  2520
      60                  5040
      64                  7560
      72                 10080
      80                 15120
      84                 20160
      90                 25200
      96                 27720
     100                 45360
     108                 50400
     120                 55440
     128                 83160
     144                110880
     160                166320
     168                221760
     180                277200
     192                332640
     200                498960
     216                554400
     224                665280
     240                720720
     256               1081080
     288               1441440
     320               2162160
     336               2882880
     360               3603600
     384               4324320
     400               6486480
     432               7207200
     448               8648640
     480              10810800
     504              14414400
     512              17297280
     576              21621600
     600              32432400
     640              36756720
     672              43243200
     720              61261200
     768              73513440
     800             110270160
     864             122522400
     896             147026880
     960             183783600
    1008             245044800
    1024             294053760
    1152             367567200
    1200             551350800
    1280             698377680
    1344             735134400
    1440            1102701600
    1536            1396755360
    1600            2095133040
    1680            2205403200
    1728            2327925600
    1792            2793510720
    1920            3491888400
    2016            4655851200
    2048            5587021440
    2304            6983776800
    2400           10475665200
    2688           13967553600
    2880           20951330400
    3072           27935107200
    3360           41902660800
    3456           48886437600
    3584           64250746560
    3600           73329656400
    3840           80313433200
    4032           97772875200
    4096          128501493120
    4320          146659312800
    4608          160626866400
    4800          240940299600
    5040          293318625600
    5376          321253732800
    5760          481880599200
    6144          642507465600
    6720          963761198400
    6912         1124388064800
    7168         1606268664000
    7200         1686582097200
    7680         1927522396800
    8064         2248776129600
    8192         3212537328000
    8640         3373164194400
    9216         4497552259200
   10080         6746328388800
   10368         8995104518400
   10752         9316358251200
   11520        13492656777600
   12288        18632716502400
   12960        26985313555200
   13440        27949074753600
   13824        32607253879200
   14336        46581791256000
   14400        48910880818800
   15360        55898149507200
   16128        65214507758400
   16384        93163582512000
   17280        97821761637600
   18432       130429015516800
   20160       195643523275200
   20736       260858031033600
   21504       288807105787200
   23040       391287046550400
   24576       577614211574400
   25920       782574093100800
   26880       866421317361600
   27648      1010824870255200
   28672      1444035528936000
   28800      1516237305382800
   30720      1732842634723200
   32256      2021649740510400
   32768      2888071057872000
   34560      3032474610765600
   36864      4043299481020800
   40320      6064949221531200
   41472      8086598962041600
   43008     10108248702552000
   46080     12129898443062400
   48384     18194847664593600
   49152     20216497405104000
   51840     24259796886124800
   53760     30324746107656000
   55296     36389695329187200
   57600     48519593772249600
   61440     60649492215312000
   62208     72779390658374400
   64512     74801040398884800
   65536    106858629141264000
   69120    112201560598327200
   73728    149602080797769600
   80640    224403121196654400
   82944    299204161595539200
   86016    374005201994424000
   92160    448806242393308800
   96768    673209363589963200
   98304    748010403988848000
  103680    897612484786617600

Part 3

最后，我们可以完善开头的表格了：

\color{red} n \le \color{red} \max\{\omega(n)\} \color{red} \text{Example} \color{red} n \le \color{red} \max\{\omega(n)\} \color{red} \text{Example}
\color{blue}10^{1} 2 6 \color{blue}10^{10} 10 6469693230
\color{blue}10^{2} 3 30 \color{blue}10^{11} 10 6469693230
\color{blue}10^{3} 4 210 \color{blue}10^{12} 11 200560490130
\color{blue}10^{4} 5 2310 \color{blue}10^{13} 12 7420738134810
\color{blue}10^{5} 6 30030 \color{blue}10^{14} 12 7420738134810
\color{blue}10^{6} 7 510510 \color{blue}10^{15} 13 304250263527210
\color{blue}10^{7} 8 9699690 \color{blue}10^{16} 13 304250263527210
\color{blue}10^{8} 8 9699690 \color{blue}10^{17} 14 13082761331670030
\color{blue}10^{9} 9 223092870 \color{blue}10^{18} 15 614889782588491410
\color{red} n \le \color{red} \max\{d(n)\} \color{red} \text{Example} \color{red} n \le \color{red} \max\{d(n)\} \color{red} \text{Example}
\color{blue}10^{1} 4 6 \color{blue}10^{10} 2304 6983776800
\color{blue}10^{2} 12 60 \color{blue}10^{11} 4032 97772875200
\color{blue}10^{3} 32 840 \color{blue}10^{12} 6720 963761198400
\color{blue}10^{4} 64 7560 \color{blue}10^{13} 10752 9316358251200
\color{blue}10^{5} 128 83160 \color{blue}10^{14} 17280 97821761637600
\color{blue}10^{6} 240 720720 \color{blue}10^{15} 26880 866421317361600
\color{blue}10^{7} 448 8648640 \color{blue}10^{16} 41472 8086598962041600
\color{blue}10^{8} 768 73513440 \color{blue}10^{17} 64512 74801040398884800
\color{blue}10^{9} 1344 735134400 \color{blue}10^{18} 103680 897612484786617600

Part 4

例题：P1463。

Chapter 2

Part 1

让我们来解决一道广为人知的题目：AT_practice_2。

对于 Subtask #1，O(n^2) 暴力即可。

对于 Subtask #2，O(n \log n) 套上归并排序等模板即可。

对于 Subtask #3，我们需要精细实现，分类讨论。

设有以下两种操作：

我们执行操作：

  2. - $a_3>a_4$，$T(4,3)$，$T(2,1)$。 - $a_3<a_4$，什么也不做。
  3. - $a_3>a_5$，$R(1,5)$，$T(2,5)$，$S(5,2)$： - $a_2<a_5$，$T(5,3)$，$R(3,4)$。 - $a_2>a_5$，$T(5,2)$，$R(1,2)$。 - $a_3<a_5$，$T(2,5)$，$R(3,4)$，$S(5,2)$ 后讨论同上。 
#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>

using namespace std;

char s[27];

bool cmp(char x, char y)
{
  cout<<"? "<<x<<' '<<y<<endl;
  char res;
  cin>>res;
  if(res=='<') return true;
  return false;
}

void st(int l, int r)
{
  if(l==r) return;
  int lmid=(l+r)/2,rmid=lmid+1;
  st(l,lmid); st(rmid,r);
  char tmp[27]={0};
  int p1=l,p2=rmid,p3=l;
  while(p1!=rmid&&p2!=r+1)
  {
    if(cmp(s[p1],s[p2])) tmp[p3]=s[p1],p1++,p3++;
    else tmp[p3]=s[p2],p2++,p3++;
  }
  while(p1<rmid) tmp[p3]=s[p1],p1++,p3++;
  while(p2<r+1) tmp[p3]=s[p2],p2++,p3++;
  for(int i=l;i<=r;i++) s[i]=tmp[i];
}

int main(void)
{
  int N,Q,i,j;

  scanf("%d%d", &N, &Q);

  for(i=0;i<N;i++) s[i] = (char)('A' + i);

  if(N==5)
  {
    if(!cmp('A','C')) swap(s[0],s[2]);
    if(!cmp('B','D')) swap(s[1],s[3]);
    if(!cmp(s[2],s[3])) swap(s[2],s[3]),swap(s[0],s[1]);
    if(!cmp(s[2],'E'))
    {
      if(!cmp(s[0],'E')) s[4]=s[3],s[3]=s[2],s[2]=s[1],s[1]=s[0],s[0]='E';
      else s[4]=s[3],s[3]=s[2],s[2]=s[1],s[1]='E';
      if(!cmp(s[2],s[1]))
      {
        if(!cmp(s[2],s[3])) swap(s[2],s[3]);
      }
      else
      {
        if(!cmp(s[2],s[0])) swap(s[2],s[1]);
        else swap(s[2],s[1]),swap(s[1],s[0]);
      }
    }
    else
    {
      if(!cmp(s[3],'E')) s[4]=s[3],s[3]='E';
      if(!cmp(s[1],s[2]))
      {
        if(!cmp(s[1],s[3])) swap(s[1],s[2]),swap(s[2],s[3]);
        else swap(s[1],s[2]);
      }
      else
      {
        if(!cmp(s[1],s[0]));
        else swap(s[1],s[0]);
      }
    }
  }
  else st(0,N-1);

  printf("! %s\n", s);
  fflush(stdout);

  return 0;
}

Part 2

根据这道题目的算法，我们可以证明，比较排序的最低复杂度为 O(n \log n)：

设有 n 个元素（不妨设它们构成 1 \sim n 的一个排列）需要排序。

很明显，输入的 n 个元素的排列顺序有 n! 种可能。

设一共比较了 k 次，则我们可以把 n! 种可能分为 2^k 类，时间复杂度为 O(k)。

为了完成比较排序，我们需要把每种可能都区分开，即 2^k \ge n!。

上述不等式解得 k \ge O(n \log n)，故比较排序的最低复杂度为 O(n \log n)。

Part 3

例题：P10750。

Chapter 3

Part 1

下面讨论如何使用 C++ 手写值域超大（2^m，其中 m=LONG_DOUBLE_MAX）且不掉精度（long double 精度）的数据类型 Log。

考虑对一个数 x 存储 \log_2 x。

对于乘法和除法（2^a \times 2^b，a>b），直接上对数运算性质。

对于加法和减法（2^a+2^b，a>b），相差倍数太大（>2^{100}）的可以直接返回较大数，否则用乘法分配率提取 2^b 后复原再相加。

```cpp struct Log { long double x; }; const long double ACC=100; Log operator+(Log a,Log b) { if(a.x<b.x) swap(a,b); if(a.x-b.x>ACC) return a; long double res=b.x; res+=log2l(powl(2,a.x-b.x)+1); return (Log){res}; } Log operator-(Log a,Log b) { if(a.x<b.x) exit(-1); if(a.x-b.x>ACC) return a; long double res=b.x; res+=log2l(powl(2,a.x-b.x)-1); return (Log){res}; } Log operator*(Log a,Log b) { return (Log){a.x+b.x}; } Log operator/(Log a,Log b) { return (Log){a.x-b.x}; } void operator+=(Log&a,Log b) { a=a+b; } void operator-=(Log&a,Log b) { a=a-b; } void operator*=(Log&a,Log b) { a=a*b; } void operator/=(Log&a,Log b) { a=a/b; } const Log ZERO=(Log){-1e9}; ``` ## Part 2 例题：[P5945](https://www.luogu.com.cn/problem/P5945)。 # Chapter 4 ## Part 1 求 $\gcd$ 是 $O(\log n)$ 的但是还不够快，怎么卡常？ 很简单：对较小的数字预先打表，可以减小一定常数。 这一优化在例题上可以将运行时间缩短 $80\%$！ ```cpp int gf[5012][5012]; void init() { for(int i=1;i<=5000;i++) for(int j=0;j<=i;j++) { if(j==0) gf[i][j]=i; else gf[i][j]=gf[j][i%j]; } for(int i=1;i<=5000;i++) for(int j=i+1;j<=5000;j++) gf[i][j]=gf[j][i]; } int gcd(int x,int y) { if(y==0) return x; if(x<=5000&&y<=5000) return gf[x][y]; return gcd(y,x%y); } ``` ## Part 2 例题：[P2065](https://www.luogu.com.cn/problem/P2065)。