Atcoder abc131

Atcoder abc131"/>

Atcoder abc131

C
容斥原理 要注意同时能被CD整除的数应该是x%gcd(C,D) == 0
D
排序后贪心
这个题的难度比400分要低
E
容易想到将1点放在中心，其他点像星型连接1点，是K的上限
然后要观察到每连接两个点将当前的k值减一，就容易构造
F
xy坐标系拆开坐标建图，这个思路很有用
如果（x,y）坐标存在，在点x与点y之间连一条无向边
加一个点的操作就转换为：
如果存在x0,y0,x1,y1且(x0,y0)(y0,x1)(x1,y1)有边相连，(x0,y1)没有边相连，将x0与y1连起来
可以发现，只要在一个连通块里面的 x i x_i xi​点与 y j y_j yj​点不直接相连，总能在若干次原操作后对这两个点进行一次原操作
所以对于 x i x_i xi​点而言，可以增加的操作是连通块内y点的数量-原来与 x i x_i xi​点连接的y点的数量

# -*- coding: utf-8 -*-
# @time     : 2023/6/2 13:30
# @author   : yhdu@tongwoo
# @desc     :
# @file     : atcoder.py
# @software : PyCharm
import bisect
import copy
import sys
from sortedcontainers import SortedList
from collections import defaultdict, Counter, deque
from functools import lru_cache, cmp_to_key
import heapq
import math
sys.setrecursionlimit(100010)def main():items = sys.version.split()if items[0] == '3.10.6':fp = open("in.txt")else:fp = sys.stdinn = int(fp.readline())N = 100005fa = [i for i in range(N * 2 + 2)]def get_fa(x):if x == fa[x]:return xfa[x] = get_fa(fa[x])return fa[x]gx = [set() for _ in range(N + 1)]for i in range(n):x, y = map(int, fp.readline().split())gx[x].add(y + N)fx, fy = get_fa(x), get_fa(y + N)if fx != fy:fa[fx] = fydsu = defaultdict(list)for i in range(1, N + 1):dsu[get_fa(i)].append(i)for i in range(1, N + 1):dsu[get_fa(i + N)].append(i + N)ans = 0for fi, t_list in dsu.items():x_list, y_list = [x for x in t_list if x <= N], [x for x in t_list if x > N]yn = len(y_list)for x in x_list:ans += yn - len(gx[x])print(ans)if __name__ == "__main__":main()