T1 math
题目大意：求$\sum\limits_{i=1}^n (-1)^{\sum\limits_{j=1}^m d(i\times j)}$，其中$d(i)$表示$i$的因数个数。$n\leq 10^7,m\leq 10^{14}$。
容易想到我们只需要看幂的奇偶即可。发现只有当$i\times j$是完全平方数时因数个数为奇数，其余情况均为偶数。于是我们可以求值域内完全平方数个数。
考虑将$i$化成$p\times q^2$的形式，$j$化成$p\times k^2$的形式。$k$即为值域内完全平方数的个数。对于每个$i$求$p$的复杂度是$O(n\sqrt n)$的；加速求$p$可以使用线性筛，时间复杂度为$O(n)$。
代码：
#include<cstdio>
#include<iostream>
#include<cmath>
#define int long long
using namespace std;
const int N=10000005;
int n,m,vis[N],ans;
signed main()
{
cin>>n>>m;
for (int i=1;i<=n;i++)
{
if (vis[i]) continue;
int q=sqrt(n/i),k=sqrt(m/i);
if (k%2) ans-=q;
else ans+=q;
for (int j=1;j<=q;j++)
vis[i*j*j]=1;
}
cout<<ans;
return 0;
}
T2 osu
题目大意：二维平面上会依次出现$n$个坐标为$(x_i,y_i)$的点，每个点出现的时间为$t_i$。人一开始在$(0,0)$。只有当人恰好在$t_i$时刻经过$(x_i,y_i)$才算经过一点。问为使人经过不少于$k$个点的速度最大值的最小值。设$ans=\frac{a\sqrt b}{c}$，请输出$a,b,c$的值。$n\leq 2000$。
最大值最小不难想到二分答案；因为$n$很小，所以check的时候可以考虑dp。时间复杂度$O(n^2 \log n)$。
关于$a,b,c$的处理可以看代码。
代码：
#include<cstdio>
#include<iostream>
#include<cmath>
#define sqr(x) ((x)*(x))
using namespace std;
const int N=2005;
const double eps=1e-4;
double ans,dis[N][N],l,r;
int p,q,f[N],g[N],n,k,a,b,c;
int t[N],x[N],y[N];
inline int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline int gcd(int x,int y){
return y==0?x:gcd(y,x%y);
}
inline bool check(double mid)
{
ans=0;
for (int i=0;i<=n;i++) f[i]=0;
for (int i=1;i<=n;i++)
{
for (int j=0;j<i;j++)
if (dis[j][i]<=mid&&f[j]+1>f[i])
f[i]=f[j]+1,g[i]=j;
if (f[i]>=k)
{
for (int x=i;g[x];x=g[x])
if (dis[g[x]][x]>ans)
ans=dis[g[x]][x],p=g[x],q=x;
return 1;
}
}
return 0;
}
int main()
{
n=read();k=read();
for (int i=1;i<=n;i++)
t[i]=read(),x[i]=read(),y[i]=read();
for (int i=0;i<n;i++)
for (int j=i+1;j<=n;j++)
{
dis[i][j]=sqrt(sqr(x[i]-x[j])+sqr(y[i]-y[j]))*1.0/(t[j]-t[i]);
r=max(r,dis[i][j]);
}
r+=eps;
while(r-l>eps)
{
double mid=(l+r)/2.0;
if (check(mid)) r=mid;
else l=mid;
}
a=1;b=sqr(x[p]-x[q])+sqr(y[p]-y[q]);c=t[q]-t[p];
for (int i=2;i<=sqrt(b);i++)
while(!(b%(i*i))) a*=i,b/=i*i;
int k=gcd(a,c);
printf("%d %d %d",a/k,b,c/k);
return 0;
}
T3 map
题目大意：给定一张含$n$个点$m$条边的无向图。定义一个好点对$(a,b)$指$a$到$b$至少有两条不相交路径。$q$次询问，每次新增加一边$(x,y)$，问新增加的好点对的个数之和。每次询问独立。$n,q\leq 2\times 10^5,m\leq 4\times 10^5$。
首先对图缩点，这样图就变成了一棵树。每次新增加一边$(x,y)$，这样树上就会出现一个环，我们考虑这个环对答案的贡献。可以发现如果两个点在加入边之前不在一个环中，但是加边之后在一个环中，那么这个点对就对答案有贡献；而先前就在一个环中的点对对答案是没有贡献的。我们可以考虑总的点对个数减去本身已经在一个环内的点对个数。倍增可以在$\log n$时间内解决问题。时间复杂度$O(q\log n)$。
代码：
#include<iostream>
#include<cstdio>
#include<vector>
#define int long long
using namespace std;
const int N=400005;
int n,m,q,x[N*2],y[N*2],ans;
int size[N],dfn[N],low[N],co[N],st[N],tot,tt,top;
int fa[N][21],sum[N],qsum[N],dep[N];
int head[N],Head[N],Cnt,cnt;
vector<int> v[N];
struct node{
int next,to;
}edge[N*4],Edge[N*4];
inline int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
inline void add(int from,int to)
{
edge[++cnt]=(node){head[from],to};
head[from]=cnt;
}
inline void Add(int from,int to)
{
Edge[++Cnt]=(node){Head[from],to};
Head[from]=Cnt;
}
inline void tarjan(int now,int f)
{
dfn[now]=low[now]=++tot;
st[++top]=now;
for (int i=Head[now];i;i=Edge[i].next)
{
int to=Edge[i].to;
if ((i%2==0&&f==i-1)||(i%2==1&&f==i+1)) continue;
if (!dfn[to]) tarjan(to,i),low[now]=min(low[now],low[to]);
else if (!co[to]) low[now]=min(low[now],dfn[to]);
}
if (low[now]==dfn[now])
{
tt++;
while(st[top]!=now)
size[tt]++,co[st[top--]]=tt;
size[tt]++;co[st[top--]]=tt;
}
}
inline void dfs(int now,int f)
{
dep[now]=dep[f]+1;fa[now][0]=f;
sum[now]=sum[f]+size[now];
qsum[now]=qsum[f]+size[now]*(size[now]-1)/2;
for (int i=1;i<=19;i++)
fa[now][i]=fa[fa[now][i-1]][i-1];
for (int i=head[now];i;i=edge[i].next)
if (edge[i].to!=f) dfs(edge[i].to,now);
}
inline int LCA(int x,int y)
{
if (dep[x]<dep[y]) swap(x,y);
for (int i=19;i>=0;i--)
if (dep[fa[x][i]]>=dep[y]) x=fa[x][i];
if (x==y) return x;
for (int i=19;i>=0;i--)
if (fa[x][i]!=fa[y][i]) x=fa[x][i],y=fa[y][i];
return fa[x][0];
}
signed main()
{
n=read();m=read();q=read();
for (int i=1;i<=m;i++)
{
x[i]=read();y[i]=read();
Add(x[i],y[i]);Add(y[i],x[i]);
}
tarjan(1,0);
for (int i=1;i<=m;i++)
{
int xx=co[x[i]],yy=co[y[i]];
if (xx!=yy) add(xx,yy),add(yy,xx);
}
dfs(co[1],0);
while(q--)
{
int a=read(),b=read();
a=co[a],b=co[b];
int l=LCA(a,b);
int s=sum[a]+sum[b]-2*sum[l]+size[l];
int ss=qsum[a]+qsum[b]-2*qsum[l]+size[l]*(size[l]-1)/2;
ans+=s*(s-1)/2-ss;
}
printf("%lld",ans*2);
return 0;
}
T4 circular
题目大意：在一个长度为$m$的环上有$n$条线段$[l_i,r_i]$。问最多能选取多少个不相交的线段。
相似的做法：[[SCOI2015]国旗计划](https://www.luogu.com.cn/problem/P4155)
首先破环成链。先考虑暴力的做法：每次选取起始线段$i$，然后不停跳合法的$nxt$，直到不能跳为止；然后取最大值。而我们可以优化跳$nxt$的过程，显然倍增可以将复杂度由$n^2$降到$n\log^2 n$。
代码：
#include<cstdio>
#include<algorithm>
#include<iostream>
using namespace std;
const int N=200005;
const int inf=0x3f3f3f3f;
int n,m,f[N][20],st[N],vis[N],top,cnt,ans;
struct node{
int l,r;
}s[N],q[N];
inline int read()
{
int x=0,f=1;char ch=getchar();
while(!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}
while(isdigit(ch)){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
bool cmp(node x,node y){
return x.l==y.l?x.r<y.r:x.l<y.l;
}
inline bool check(int x,int i)
{
int p=i;
for (int j=0;j<=18;j++)
if ((x>>j)&1) p=f[p][j];
return q[i].l+m>=q[p].r;
}
int main()
{
m=read();n=read();
for (int i=1;i<=n;i++)
{
s[i].l=read();s[i].r=read();
if (s[i].r<s[i].l) s[i].r+=m;
}
for (int i=1;i<=n;i++)
s[i+n].l=s[i].l+m,s[i+n].r=s[i].r+m;
n*=2;
sort(s+1,s+n+1,cmp);
for (int i=1;i<=n;i++){
while(top&&s[st[top]].r>=s[i].r) vis[st[top--]]=1;
st[++top]=i;
}
for (int i=1;i<=n;i++)
if (!vis[i]) q[++cnt]=s[i];
int p=1;q[cnt+1].l=inf;q[0].r=inf;
for (int i=1;i<=cnt;i++)
{
while(p<=cnt&&q[p].l<q[i].r) p++;
if (p>cnt) break;
f[i][0]=p;
}
for (int j=1;j<=18;j++)
for (int i=1;i<=cnt;i++)
f[i][j]=f[f[i][j-1]][j-1];
for (int i=1;i<=cnt;i++)
{
int l=0,r=n/2,p;
while(l<=r)
{
int mid=(l+r)>>1;
if (check(mid,i)) p=mid,l=mid+1;
else r=mid-1;
}
ans=max(ans,p+1);
}
printf("%d",ans);
return 0;
}