は？ —— ロキ
A
给定整数 \(L,R\ (L\ \le\ R)\)，请计算满足以下条件的整数对 \((x,y)\) 的数量：
- \(L\ \le\ x,y\ \le\ R\)
- 设 \(g\) 是 \(x,y\) 的最大公约数，则满足以下条件：
- \(g\ \neq\ 1\) 且 \(\frac{x}{g}\ \neq\ 1\) 且 \(\frac{y}{g}\ \neq\ 1\)
solution:
简单莫反。
先容斥一下，答案为 \((R - L + 1) ^ 2\) 减去满足不满足条件的数对数。
那么现在需要求的是符合 \(\gcd(x, y) = 1 \space \operatorname{or} \space y | x \space \operatorname{or} \space x | y\) 的数对数。
分成两块处理，先考虑处理 \(\gcd\) 的条件，即要求：
\[ans=\sum_{i = L}^{R} \sum_{j = L}^{R} \left [ \gcd (i,j) = 1 \right ] \]令 $$f(n, m) = \sum_{i=1}^{n} \sum_{j=1} ^{m}\left [ gcd(i,j) = 1 \right ] $$
简单莫反得到 $$f(n,m) = \sum_{d=1}^{\min(n,m)}\mu(d)\left \lfloor \frac{n}{d} \right \rfloor \left \lfloor \frac{m}{d}\right \rfloor $$
而原式可以通过容斥转化：$$ans=f(R,R) - 2f(L-1,R) + f(L-1, L-1)$$
这题数据范围较小可以不用整除分块，线性筛出 \(\mu\) 后循环累加即可。
接下来考虑 \(y | x \space \operatorname{or} \space x | y\) 这一条件。枚举 \(x\)，答案累加 \(\large\left\lfloor\frac{R}{x}\right\rfloor\) 即可。
code:
#include<iostream>
#include<fstream>
#include<algorithm>
#pragma GCC optimize(3,"Ofast","inline")
#define int long long
using namespace std;
const int maxn = 1000000;
int n, m, ans, ret;
int mu[maxn + 5], prime[maxn + 5], cnt;
bool vis[maxn + 5];
int prework(){
mu[1] = 1;
for(int i = 2; i <= maxn; i ++){
if(!vis[i])
prime[++ cnt] = i, mu[i] = -1;
for(int j = 1; j <= cnt && i * prime[j] <= maxn; j ++){
vis[i * prime[j]] = true;
if(i % prime[j] == 0)
break;
mu[i * prime[j]] = -mu[i];
}
}
return 0;
}
int solve1(int l, int r){
int res = 0;
for(int i = 1; i <= l; i ++)
res += mu[i] * (l / i) * (r / i);
return res;
}
int solve2(int l, int r){
int res = 0;
if(l == 1) l ++;
for(int i = l; i <= r; i ++)
res += r / i;
return res;
}
signed main(){
cin >> n >> m;
prework();
ans = (m - n + 1) * (m - n + 1);
ret = solve1(m, m) - 2 * solve1(n - 1, m) + solve1(n - 1, n - 1);
ans -= ret;
ans -= 2 * solve2(n, m);
ans += (m - n + 1);
if(n == 1)
ans --;
cout << ans;
return 0;
}
B
给定一张无向联通图，多次询问求删除一条边或者删除一个点后两点的连通性。
solution:
维护连通性问题一般使用圆方树但是我不会所以我用 Tarjan 缩点暴力。
删除一条边和删除一个点是无关的两种询问所以分开讨论。
删除边后连通性
首先很显然，如果删除的这条边不是这张图的桥，那么删除这条边不会有影响。所以先 Tarjan 找出所有的桥。
对 e-dcc 缩点，形成一棵树。问题变成，树上询问两点间路径是否经过一条给定边。
以任意一点为根得到这棵树的 dfs 序。
对于每次询问的割边，设深度较深的点为 \(u\)，较深的为 \(v\) 当前询问的两点为 \(a\)、\(b\)。那么如果 \(a\)、\(b\) 间的路径要经过 \((u,v)\) ，则 \(a\)、\(b\) 必有一点在 \(u\) 的子树内，而另一点必不在 \(u\) 子树内。根据 dfs 序判断即可。
删除点后连通性
复杂很多。同理，如果删除的这个点不是这张图的割点，那么删除这个点不会有影响。Tarjan 找出所有的割点。
因为每个割点都可能在多个 v-dcc 内，所以对每个割点建立新的虚点，连向其所在的 v-dcc，然后对 v-dcc 缩点，形成一棵树，问题变成，树上询问两点间路径是否经过一个给定点。
以任意一点为根得到这棵树的 dfs 序。
对于每次询问的割点，如果 \(a\)、\(b\) 的路径要经过 \(u\)，则有两种情况：
-
这条路径穿过点 \(u\) 到 \(u\) 上方的点。此时\(a\)、\(b\) 必有一点在 \(u\) 的子树内，而另一点必不在 \(u\) 子树内。根据 dfs 序判断即可。
-
这条路径上深度最深的点为点 \(u\)，即点 \(u\) 为 \(a\)、\(b\) 两点的 lca。求出 \(a\)、\(b\) 的 lca 即可。
需要注意的是这题空间卡的很死需要用树链剖分求 lca。（或者用 Tarjan 求 lca 当然我也不会）
code :
这份代码可读性并不高因为为了卡空间很多数组被我多次使用，实际上我也有一份 MLE 但是可读性较高的代码如果有需要我再贴出来。
#include<iostream>
#include<fstream>
#include<algorithm>
#include<vector>
#include<set>
#include<cstring>
using namespace std;
vector<int> edge[200005];
vector<int> dcc[100005];
struct edge_e{
int x1, x2;
edge_e(int a, int b){
x1 = a, x2 = b;
}
};
bool operator < (edge_e u, edge_e v){
return u.x1 == v.x1 ? u.x2 < v.x2 : u.x1 < v.x1;
}
set<edge_e> deled;
bool dele[100005];
int n, m;
int dfn[200005], low[200005], tim, cntdlt, num;
int st[100005], top;
bool vis[100005];
int tarjan(int u, int lst){
dfn[u] = low[u] = ++ tim;
st[++ top] = u;
int flag = 0;
for(int i = 0, v; i < edge[u].size(); i ++){
v = edge[u][i];
if(v == lst) continue;
if(dfn[v])
low[u] = min(low[u], dfn[v]);
else{
tarjan(v, u);
low[u] = min(low[u], low[v]);
if(low[v] > dfn[u])
deled.insert(edge_e(min(u, v), max(u, v)));
if(low[v] >= dfn[u]){
flag ++;
if(lst != 0 || flag > 1) dele[u] = true;
cntdlt ++;
int z;
do{
z = st[top --];
dcc[cntdlt].push_back(z);
}while(z != v);
dcc[cntdlt].push_back(u);
}
}
}
return 0;
}
int tot, tot2, id2[100005];
int l[100005], r[100005], l1[200005], r1[200005];
int dfs2(int u, int lst, int idd){
vis[u] = 1, id2[u] = idd, l[idd] = idd;
for(int i = 0, v; i < edge[u].size(); i ++){
v = edge[u][i];
if(v == lst || vis[v]) continue;
if(deled.find(edge_e(min(u, v), max(u, v))) != deled.end()){ dfs2(v, u, ++ tot2); continue;}
dfs2(v, u, idd);
}
r[idd] = max(r[idd], tot2);
return 0;
}
int dep[200005], timing;
int faa[200005], siz[200005], son[200005];
int dfs11(int u){
siz[u] = 1, dfn[u] = ++timing, l1[u] = timing;
for(int i = 0; i < edge[u].size(); i ++){
int v = edge[u][i];
if(v == faa[u])
continue;
faa[v] = u, dep[v] = dep[u] + 1;
dfs11(v);
siz[u] += siz[v];
if(siz[v] > siz[son[u]])
son[u] = v;
}
r1[u] = timing;
return 0;
}
int dfs12(int u, int tp){
low[u] = tp;
if(son[u])
dfs12(son[u], tp);
for(int i = 0; i < edge[u].size(); i ++){
int v = edge[u][i];
if(v == faa[u] || v == son[u])
continue;
dfs12(v, v);
}
return 0;
}
int getlca(int u, int v){
while(low[u] != low[v]){
if(dep[low[u]] < dep[low[v]])
swap(u, v);
u = faa[low[u]];
}
if(u == v)
return u;
if(dep[u] > dep[v])
swap(u, v);
return u;
}
int q;
int main(){
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> n >> m;
for(int i = 1, u, v; i <= m; i ++)
cin >> u >> v, edge[u].push_back(v), edge[v].push_back(u);
tarjan(1, 0);
dfs2(1, 0, ++ tot2);
num = cntdlt;
memset(st, 0, sizeof(st));
for(int i = 1; i <= n; i ++)
edge[i].clear();
for(int i = 1; i <= n; i ++)
if(dele[i]) st[i] = ++ num;
for(int i = 1; i <= cntdlt; i ++){
for(int j = 0; j < dcc[i].size(); j ++){
int x = dcc[i][j];
if(dele[x]) edge[i].push_back(st[x]), edge[st[x]].push_back(i);
else st[x] = i;
}
}
memset(low, 0, sizeof(low)), memset(dfn, 0, sizeof(dfn));
dfs11(1), dfs12(1, 1);
cin >> q;
for(int i = 1, opt, u, v, w, xx; i <= q; i ++){
cin >> opt;
if(opt == 1){
cin >> u >> v >> w >> xx;
if(w > xx) swap(w, xx);
if(deled.find(edge_e(w, xx)) == deled.end()){
cout << "yes\n";
continue;
}
int x = id2[u], y = id2[v];
if(x == y){
cout << "yes\n"; continue;
}
int ll = max(l[id2[w]], l[id2[xx]]), rr = min(r[id2[w]], r[id2[xx]]);
if((ll <= x && x <= rr && ll <= y && y <= rr) || ((ll > x && ll > y) || (rr < x && rr < y) || (ll > x && rr < y) || (ll > y && rr < x))){
cout << "yes\n"; continue;
}
cout << "no\n";
}
if(opt == 2){
cin >> u >> v >> w;
if(!dele[w]){ cout << "yes\n"; continue; }
w = st[w], u = st[u], v = st[v];
int x = getlca(u, v), y;
if(w == x){ cout << "no\n"; continue; }
int ll = l1[w], rr = r1[w];
x = dfn[u], y = dfn[v];
if((ll <= x && x <= rr && ll <= y && y <= rr) || ((ll > x && ll > y) || (rr < x && rr < y) || (ll > x && rr < y) || (ll > y && rr < x))){
cout << "yes\n"; continue;
}
cout << "no\n";
}
}
return 0;
}