约数

Solution

20分

暴力求值.

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define M 700000
#define N 10000005
using namespace std;
typedef long long ll;
ll d[N],ans;
int f[N],p[M],a[M],t[M],n,m,cnt;
inline void prime(){
     for(int i=2;i<=n;++i){
        if(!f[i]){
			p[++cnt]=f[i]=i;
        }
        for(int j=1;j<=cnt&&i*p[j]<=n;++j){
            f[i*p[j]]=p[j];
            if(!(i%p[j])) break;
        }        
    }
}
inline void func_d(int k){
	d[k]=1;
	int x=k,y,cnt;
	while(x>1){
		cnt=0;y=f[x];
		while(!(x%y))
			x/=y,++cnt;
		d[k]*=(cnt+1ll);
	}
}
inline void dfs(int u,int x,int k){
	if(u>m){
		ans+=d[x];return;
	}
	dfs(u+1,x,k);
	for(int i=1;i<=t[u];++i){
		x*=a[u];dfs(u+1,x,k);
	}
} 
inline void func_ans(int k){
	m=0;
	int x=k;
	while(x>1){
		a[++m]=f[x];t[m]=0;
		while(!(x%a[m]))
			x/=a[m],++t[m];
	}
	dfs(1,1,k); 
}
inline void Aireen(){
	scanf("%d",&n);
	prime();
	for(int i=1;i<=n;++i) func_d(i);
	for(int i=1;i<=n;++i) func_ans(i);
	printf("%lld\n",ans);
}
int main(){
	freopen("divisor.in","r",stdin);
	freopen("divisor.out","w",stdout);
	Aireen();
	fclose(stdin);
	fclose(stdout);
	return 0;
}

100分

把式子展开为\(\sum_{i=1}^n\sum_{p|i}\sum_{q|p}1\).
即\(q\times\lfloor\frac{p}{q}\rfloor\times\lfloor\frac{i}{p}\rfloor\leq{n}\),即求满足\(xyz\leq{n}(x,y,z\in{N^{+}})\)的三元组个数.
假设\(x\leq{y}\leq{z}\),枚举加上组合,容斥求即可.

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
typedef long long ll;
ll n;
inline ll ans1(){
	ll ret=0;
	for(ll i=1;i*i*i<=n;++i)
		for(ll j=i;i*j*j<=n;++j)
			ret+=n/(i*j)-j+1;
	return ret; 
}
inline ll ans2(){
	ll ret=0;
	for(ll i=1;i*i<=n;++i)
		ret+=n/(i*i);
	return ret; 
}
inline ll ans3(){
	ll ret=0;
	for(ll i=1;i*i*i<=n;++i)
		++ret;
	return ret;
}
inline void Aireen(){
	scanf("%lld",&n);
	printf("%lld\n",ans1()*6ll-ans2()*3ll-ans3()*2ll);
}
int main(){
	freopen("divisor.in","r",stdin);
	freopen("divisor.out","w",stdout);
	Aireen();
	fclose(stdin);
	fclose(stdout);
	return 0;
}

最小生成树

Solution

100分

如果选择了第\(i\)次操作的边,必然也选择了\((A_i,B_i)=C\)这条边.
那么\(A,B\)同属一个集合.
所以\((A_i,B_i)=C_i,(B_i,A_i+1)=C_i+1\)可以看做\((A_i,A_i+1)=C_i+1\).
同理,每次加边操作可以看为\((A_i,B_i)=C_i,(A_i,A_i+j)=C_i+2j-1,(B_i,B_i+j)=C_i+2j\).
后两种每次加边\(O(n)\).
所以设\(d[i]\)表示\((i,i+1)\)之间的最短路径长度.
\(d[i]=min\{d[i],d[i-1]+2\}\).
所以只需初始化\(d[A_i]=C_i+1,d[B_i]=C_i+2\).
所有操作结束后,循环两圈求\(d[i]\)最小值.

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define N 200005
#define INF 2000000000
#define min(a,b) a