数论。

Table of Contents

  1. Description
  2. Solution

Description

对于两个正整数$a,b$，这样定义函数$d(a,b)$：每次操作可以选择一个质数$p$，将$a$变成$a \times p$或$a/p$，如果选择变成$a/p$就要保证$p$是$a$的约数，$d(a,b)$表示将$a$变成$b$所需的最少操作次数。例如$d(69,42)=3$。

现在给出$n$个正整数$A_1,A_2,\ldots,A_n$，对于每个$i (1 \le i \le n)$，求最小的$j(1 \le j \le n)$使得$i \ne j$且$d(A_i,A_j)$最小。

Solution

不难观察出$d$就是各素因子指数差的绝对值之和, 然而……

这样是推不出答案的.

转换一下答案形式, 记$g[i]$是$i$的素因子指数和, 我们有$d(i,j) = g[i] + g[j] - g[gcd(i,j)]$.

这样我们就可以枚举$a_i$的每个约数作为gcd, 更新答案. 预处理出一个数及其倍数的最小答案用于更新. 这样可能会导致一些数字并没有达到gcd就被用于计算答案, 但这样是不会比答案优的, 因为这会使减去的那部分$g$偏小.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>

using namespace std;

const int maxn = 1e+5 + 5;
const int maxi = 1e+6 + 1;

int n, a[maxn], tag[maxi][2];

int npr[maxi], pr[maxi], g[maxi], cnt, mindiv[maxi];
void euler() {
  for (int i = 2; i < maxi; ++i) {
    if (!npr[i]) {
      pr[++cnt] = i;
      g[i] = 1;
      mindiv[i] = i;
    }
    for (int j = 1; j <= cnt && i * pr[j] < maxi; ++j) {
      g[i * pr[j]] = g[i] + 1;
      mindiv[i * pr[j]] = pr[j];
      npr[i * pr[j]] = 1;
      if (!(i % pr[j])) break;
    }
  }
}

int lst[maxn], ind[maxn], id;
void div(int x) {
  id = 0;
  while (x != 1) {
    if (mindiv[x] == lst[id]) ind[id]++;
    else lst[++id] = mindiv[x], ind[id] = 1;
    x /= mindiv[x];
  }
}

int mul[maxi], top;
void dfs(int d, int cur) {
  if (d > id) {
    mul[++top] = cur;
    return;
  }
  for (int i = 0, m = 1; i <= ind[d]; ++i, m *= lst[d])
    dfs(d + 1, cur * m);
}

struct node
{
  int val, pos;
  node(int l_ = 0 , int r_ = 0):val(l_),pos(r_){}
  bool operator < (const node &rhs) const {
    return (val == rhs.val) ? (pos < rhs.pos) : (val < rhs.val);
  }
};
struct Answer
{
  static const int inf = 0x3f3f3f3f;
  node MinFir, MinSec;
  Answer() {MinFir = node(inf, 0); MinSec = node(inf, 0);}
  void update(int vl, int ps) {
    node p = node(vl, ps);
    if (p < MinFir) MinSec = MinFir, MinFir = p;
    else if (p < MinSec) MinSec = p;
  }
}mem[maxi];

int main() {
  euler();
  scanf("%d", &n);
  for (int i = 1; i <= n; ++i) {
    scanf("%d", &a[i]);
    if (!tag[a[i]][0])
      tag[a[i]][0] = i;
    else if (!tag[a[i]][1])
      tag[a[i]][1] = i;
  }
  for (int i = 1; i < maxi; ++i) {
    for (int j = i; j < maxi; j += i) {
      if (tag[j][0])
        mem[i].update(g[j], tag[j][0]);
      if (tag[j][1])
        mem[i].update(g[j], tag[j][1]);
    }
  }
  for (int i = 1; i <= n; ++i) {
    div(a[i]);
    top = 0;
    dfs(1, 1);
    node now = node(0x3f3f3f3f, 0);
    for (int j = 1; j <= top; ++j) {
      if (mem[mul[j]].MinFir.pos == i)
        now = min(now, node(g[a[i]] + mem[mul[j]].MinSec.val - 2 * g[mul[j]], mem[mul[j]].MinSec.pos));
      else 
        now = min(now, node(g[a[i]] + mem[mul[j]].MinFir.val - 2 * g[mul[j]], mem[mul[j]].MinFir.pos));
    }
    printf("%d\n", now.pos);
  }
  return 0;
}