BZOJ 2749 && Comet OJ C1416 [HAOI2012]外星人

#include <bits/stdc++.h>
#define
#define

using namespace std;
typedef long long ll;
int T, m, pri[A], cnt;
bool bz[A]; ll f[A], p, q;

int main(int argc, char const *argv[]) {
  f[1] = 1;
  for (int i = 2; i <= B; i++) {
    if (!bz[i]) pri[++cnt] = i, f[i] = f[i - 1];
    for (int j = 1; j <= cnt and i * pri[j] <= B; j++) {
      bz[i * pri[j]] = 1;
      f[i * pri[j]] = f[i] + f[pri[j]];
      if (i % pri[j] == 0) break;
    }
  }
  cin >> T;
  while (T--) {
    scanf("%d", &m); ll ans = 1;
    while (m--) {
      scanf("%lld%lld", &p, &q);
      if (p == 2) ans--;
      ans += f[p] * q;
    }
    printf("%lld\n", ans);
  }
  return 0;
}