复试模板

进制转换

string conversion(string num, int m, int n) {
  int l = num.size(), k = 0;
  string ans = "";
  for (int i = 0; i < l;) {
    k = 0;
    for (int j = i; j < l; j++) {
      int t = (k * m + num[j] - '0') % n;
      num[j] = (k * m + num[j] - '0') / n + '0';
      k = t;
    }
    ans += (k + '0');
    while (num[i] == '0') i++;
  }
  return ans;
}

线性筛

int prime[N], n, k;
bool isprime[N];
void get_prime() {
  memset(isprime, 1, sizeof(isprime));
  for (int i = 2; i <= n; ++i) {
    if (isprime[i]) prime[k++] = i;
    for (int j = 0; j < k && i * prime[j] <= n; ++j) {
      isprime[i * prime[j]] = false;
      if (i % prime[j]) break;
    }
  }
}

并查集

int tree[N];
int find(int x) {
  if (tree[x] == x) return x;
  return tree[x] = find(tree[x]);
}
void unit(int x, int y) {
  x = find(x), y = find(y);
  if (x != y) tree[y] = x;
}
void init(int n) {
  for (int i = 1; i <= n; ++i) tree[i] = i;
}
bool same(int x, int y) { return find(x) == find(y); }

高精度

class HighPrecision {
  int num[MAX_N], len = 0;

 public:
  HighPrecision operator+(HighPrecision& b) {
    HighPrecision ans;
    int rem = 0, i = 1;
    for (; i <= this->size() && i <= b.size(); ++i) {
      int t = this->num[i] + b[i] + rem;
      ans[i] = t % 10;
      rem = t / 10;
    }
    if (i <= this->size()) {
      while (i <= this->size()) {
        int t = this->num[i] + rem;
        ans[i] = t % 10;
        rem = t / 10;
        ++i;
      }
    } else {
      while (i <= b.size()) {
        int t = b[i] + rem;
        ans[i] = t % 10;
        rem = t / 10;
        ++i;
      }
    }
    while (rem) {
      ans[i++] = rem % 10;
      rem /= 10;
    }
    ans.setSize(i - 1);
    return ans;
  }
  inline int size() const { return len; }
  inline void setSize(int x) { this->len = x; }
  inline int& operator[](int x) { return this->num[x]; }
  inline void read() {
    char ch;
    for (ch = getchar(); !isdigit(ch); ch = getchar());
    do {
      num[++len] = ch - '0';
      ch = getchar();
    } while (isdigit(ch));
    reverse(num + 1, num + len + 1);
  }
  inline void print() {
    for (int i = len; i; --i) putchar(num[i] + '0');
  }
};