第八場比賽 題解
=
>敗者死於絕望，勝者死於渴望

# [z071](https://judge.cp.ccns.io/problem/z071)：
直覺是建表，但範圍 $3⋅10^9$ 在要記憶體時就會 RE 了
而 $O(\sqrt N)$ 的**試除法**又太慢

所以就有以下的作法：

#include<bits/stdc++.h>
using namespace std;
typedef long long Int;

int const maxn = 55e3;

Int N;
bool is_p[maxn];
vector<int> prime;

int main()
{
  // sieve
  fill(is_p, is_p+maxn, true);
  is_p[1] = false;

  for(int n = 2; n < maxn; n++) {
    if(is_p[n]) prime.push_back(n);

    for(int p: prime) {
      if(n*p >= maxn) break;

      is_p[n*p] = false;
      if(n%p == 0) break;
    }
  }

  // check
  while(~scanf("%lld", &N)) {
    bool ok = N != 1;

    for(Int p: prime) {
      if(p*p > N) break;
      if(N%p == 0) { ok = false; break; }
    }

    puts(ok? "YES" : "NO");
  }

  return 0;
}

或是用 [Miller-Rabin **測試**法](https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test)也行，
傳說有幾個 liar 可以涵蓋 64-bit 整數，一直試錯的那幾隊可以去查一下 XD

# [z072](https://judge.cp.ccns.io/problem/z072)：
Sort 簡單題目。
注意 Long Long Int

#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll n, m;
vector< ll > a;
vector< ll > s;
vector< ll > ans;

int main() {
        cin >> n >> m;
        a.resize(n);
        s.resize(n);
        ans.resize(m);
        for(int i = 0; i < n; i++) cin >> a[i];
        for(int i = 0; i < n; i++) s[i] = (i == 0?0:s[i-1]) + a[i];
        for(int i = 0; i < m; i++) {
                int x, y;
                cin >> x  >> y;
                ans[i] = s[y-1] - (x == 1? 0 :s[x-2]);
        }
        sort(ans.begin(), ans.end());

        ll cnt = 0;
        for(int i = 0 ; i < m; i++) cnt += ans[i] * (i+1);
        cout << cnt << endl;
        return 0;
}

# [z073](https://judge.cp.ccns.io/problem/z073)：
令 $K_i = 1234567891011\text{..}i$ ($i \le N$)

若 $a \equiv K_{i-1} \mod 2019$
> 其中等號**左項**為右項除以 $2019$ 的餘數

則
$$
a\cdot 10^{\text{len}(i)} \equiv K_{i-1}\cdot 10^{\text{len}(i)} \mod 2019
$$
> $\text{len}(x)$ 表示 $x$ 的位數

及
$$
\begin{split}
a\cdot 10^{\text{len}(i)} + i &\equiv K_{i-1}\cdot 10^{\text{len}(i)} + i \mod 2019 \\
&\equiv K_{i}\mod 2019
\end{split}
$$

根據上述，迭代 $i$ 至 $N$ 就能算出 $K_N \text{ mod } 2019$ 了：

from math import log10

n = int(input())

a = 0
for i in range(1, n+1):
    a = (a * 10**(int(log10(i))+1) + i) % 2019

print(a)

# [z074](https://judge.cp.ccns.io/problem/z074)：
想要考圖論，不解釋。

練習重建圖，計算degree。

#include <bits/stdc++.h>
#define pii pair<int, int>
#define ff first
#define ss second

using namespace std;

int n, m, q;
vector<int> deg;
priority_queue< pair<int, pii> > edge;
vector< pii > data; 
vector<int> bs;//boss

int fboss(int x) {
  if(x == bs[x]) return x;
  return bs[x] = fboss(bs[x]);
}


int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  cin >> n >> m >> q;
  
  bs.resize(n+1);
  for(int i = 1; i <= n; i++) bs[i] = i;
  deg.resize(n+1);
  data.resize(m);
  for(int i = 0; i < m; i++) {
    int a, b;
    cin >> a >> b;
    deg[a]++, deg[b]++;
    data[i].ff = a;
    data[i].ss = b;
  }

  for(int i = 0; i < m; i++) {
    int a = data[i].ff;
    int b = data[i].ss;
    int deg_min = min(deg[a], deg[b]);
    edge.push(make_pair(deg_min, data[i]));
  }
  
  vector<int> ans;
  ans.resize(n);
  int cnt = n;
  for(int i = n-1; i >= 0; i--) {
    //rebuild
    while(!edge.empty() && edge.top().ff > i) {
      pii now = edge.top().ss; edge.pop();
      int bs_a = fboss(now.ff);
      int bs_b = fboss(now.ss);
      if(bs_a != bs_b) cnt--, bs[bs_a] = bs_b;
    }
    ans[i] = cnt-1;
  }
  for(int i = 0; i < q; i++) {
    int qq;
    cin >> qq;
  	cout << ans[qq] << endl;
  }

  return 0;
}

# [z075](https://judge.cp.ccns.io/problem/z075)：