AtCoder Beginner Contest 296 做题记录-526互联

D - M<=ab

题意：求最小的正整数，不小于 \(m\)，且能被表示为两个不大于 \(n\) 的正整数的数，不存在输出 -1。\(n,m\le10^{12}\)。

直接枚举 \(a\)，计算最小的满足 \(ab\ge m\) 的 \(b\)，如果 \(a>b\) 则后面的情况一定是重复的。时间复杂度 \(\text{O}(\sqrt n)\)。最好用 __int128 。

#include<bits/stdc++.h>
#define int __int128
using namespace std;
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-48;ch=getchar();}
	return x*f;
}
inline void print(int x){
	if(x<0)putchar('-'),x=-x;
	if(x>9)print(x/10);
	putchar(x%10+'0');
}
signed main(){
	int n=read(),m=read(),ans=n*n;
	if(n*n<m)return puts("-1"),0;
	for(int a=1;a<=n;a++){
		int b=(m+a-1)/a;
		if(b<=n&&a*b>=m)ans=min(ans,a*b);
		if(b<a)break;
	}
	print(ans);
	return 0;
}

E - Transition Game

题意：给一个 \(n\) 个点 \(n\) 条形如 \(i\rightarrow a_i\) 的有向边的图，求有多少个点在环中（包括自环）。\(n,a_i\le2\times10^5\)。

\(\text{tarjan}\) 缩点或者拓扑找环即可。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5,inf=1e18;
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-48;ch=getchar();}
	return x*f;
}
struct edge{
	int v,nxt;
}e[N*2];
int head[N],tot;
void add(int u,int v){
	e[++tot]=(edge){v,head[u]},head[u]=tot;
}
int dfn[N],low[N],in[N],a[N],val[N],col[N],rc,id;
stack<int>s;
void tarjan(int u){
	dfn[u]=low[u]=++id;s.push(u);in[u]=1;
	for(int i=head[u];i;i=e[i].nxt){
		int v=e[i].v;
		if(!dfn[v])tarjan(v),low[u]=min(low[u],low[v]);
		else if(in[v])low[u]=min(low[u],dfn[v]);
	}
	if(dfn[u]==low[u]){
		int v;rc++;
		do{v=s.top();s.pop();in[v]=0;col[v]=rc;val[rc]+=1;}while(u!=v);
	}
}
int vis[N];
int u[N],v[N];
signed main(){
	int n=read(),ans=0;
	for(int i=1;i<=n;i++){
		a[i]=read();
		if(i!=a[i])add(i,a[i]);
		else ans++;
	}
	for(int i=1;i<=n;i++){
		if(!dfn[i])tarjan(i);
	}
	for(int i=1;i<=rc;i++){
		if(val[i]>1)ans+=val[i];
	}
	printf("%lld\n",ans);
	return 0;
}