2023.8.11测试
\[\text{暑假NOIP模拟赛-4}
\]
为什么我天天挂分？？？？？？？？？
T1 数对
其实就是[ARC107D] Number of Multisets
简单容斥+莫反，但是最后10min才发现容斥写错了！！！！！
设 \(calc(l,r)\) 表示 \(x\in[1,l]\)，\(y\in[1,r]\) 的答案，那么 \(ans=calc(r,r)-calc(l-1,r)-calc(r,l-1)+calc(l-1,l-1)\)
#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1000010;
int L,R;
int v[N],prime[N],tot,mu[N];
LL ans,sum[N];
void primes()
{
mu[1]=1;
for(int i=2; i<=1e6; i++)
{
if(!v[i])
{
v[i]=i;
prime[++tot]=i;
mu[i]=-1;
}
for(int j=1; j<=tot && prime[j]<=v[i] && prime[j]<=1e6/i; j++)
{
v[i*prime[j]]=prime[j];
if(i%prime[j]==0)
break;
mu[i*prime[j]]=-mu[i];
}
}
for(int i=1; i<=1e6; i++)
sum[i]=sum[i-1]+(LL)mu[i];
}
LL calc(int n,int m)
{
LL res=1LL*n*m;
for(int l=1,r; l<=n; l=r+1)
{
r=min(n/(n/l),m/(m/l));
res-=1LL*(n/l)*(m/l)*(sum[r]-sum[l-1]);
}
for(int i=2; i<=n; i++)
res-=1LL*((n/i)+(m/i)-1);
return res;
}
int main()
{
primes();
scanf("%d%d",&L,&R);
ans=calc(R,R)-2*calc(L-1,R)+calc(L-1,L-1);
printf("%lld\n",ans);
return 0;
}
T2 小偷与警察
其实就是P4334 [COI2007] Policija
很好的点双练习题，逼我赶紧去恶补圆方树，需要赶紧修订图的连通性相关（Tarjan算法）
先跑一遍 \(\Tarjan\)，求出所有割点和割边，这步一眼。对于不是割边的边或割点的点，询问时显然直接输出yes
对于割边和割点，边双缩点和点双缩点都要做一遍？？？
不用！我们惊奇地发现一条割边的两个端点一定是割点，所以可以直接将边的询问转化为点的询问
那现在问题变成了