约数

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