【算法基础】算法优化与技巧 Collection

快读快写 和 __int128 读写模板

P10815【模板】快速读入

给你 \(n\) 个数，你需要求和并输出。数据保证对于序列的任何前缀，这个前缀的和在 32 位有符号整形的存储范围内。\(10^5 \le n \le 10^8\)

Part 0：标准读写

利用 cin 和 cout 可以得到 \(70\) 分。

Part 1：读写优化

利用这种方法可以优化到 \(75\) 分。

常见的读写优化有以下两种：

• 将 cin 和 cout 替换为 scanf 和 printf
• 利用 std::ios::sync_with_stdio(false) 解绑流绑定，不再混用两种方式的读写
• 利用 cin.tie(0) 和 cout.tie(0) 以不再自动刷新缓冲区，改为std::cout.flush() 手动刷新

Part 2：基础快读快写

inline long long read() {
  long long x = 0;
  int sgn = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') sgn *= -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = (x << 3) + (x << 1) + (ch ^ 48);
    ch = getchar();
  }
  return sgn * x;
}
inline void write(auto n){
	if (n < 0) putchar('-'),n = -n;
	if (n >= 10) write(n / 10);
	putchar(n % 10 + '0');
	return;
}

Part 3：手写栈 fread 和 fwrite 优化 getchar 基础上快读

#define ll long long
static constexpr ll _ = 1 << 20;
char buf[_], *p1, *p2;
#define gc() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, _, stdin), p1 == p2) ? EOF : *p1++)
inline auto read(){
	ll s = 0, f = 1;
	char c = gc();
	while (c < '0' || c > '9') f = (c == '-' ? -1 : 1),c = gc();
	while (c >= '0' && c <= '9') s = s * 10 + c - 48,c = gc();
	return s * f;
}

__int128 读写

Part 2 修改实现。

inline __int128 read() {
  __int128 x = 0;
  int sgn = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') sgn *= -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = (x << 3) + (x << 1) + (ch ^ 48);
    ch = getchar();
  }
  return sgn * x;
}
inline void write(__int128 n){
	if (n < 0) putchar('-'),n = -n;
	if (n >= 10) write(n / 10);
	putchar(n % 10 + '0');
	return;
}

快速幂

P1226 【模板】快速幂

给你三个整数 \(a,b,p\)，求 \(a^b\bmod p\)。 \(0\le a,b < 2^{31}\)，\(a+b>0\)，\(2 \leq p \lt 2^{31}\)

关键代码如下。

#define ll long long
#define lll __int128 
inline ll ksm(ll a, ll b, ll Mod) {
    ll z = 1;
    while (b) {
        if (b & 1) z = z * a % Mod;
        a = a * a % Mod;
        b >>= 1;
    }
    return z;
}