头像

zhangjianjunab


访客:1170

在线 



QAQ 237行的代码 QAQ

打了我一个下午啊啊啊啊。

题目

题目

我的做法

基础做法

机房大佬CLB提示我这道题目是虚树(当然我的做法不知道是不是虚树,反正虚就对了),于是我发现对于以下的图:在这里插入图片描述
在对外显示上,两个蓝点的LCA是可以代替这两个蓝点的,然后,我们的做法出来了,对于两个点,维护他们两个的LCA,如果一个虚点(即不是真的异象石的位置)只有一个点(不管实的虚的),那么就将这个点连到其父亲上面。

特别的,因为(个人觉得)难以维护目前树上没有父亲的点,所以默认$1$点永远存在。(当然后来发现没有父亲的点最多一个,其实用个$root$存一下就行了)

当然,还是有不少细节的。

给上一个图(绿色为虚点,蓝色为实点,黑色为原树上的边,红色为虚树上的边):

在这里插入图片描述

注:一下内容的儿子、父亲、LCA可能有点难分辨是实树上的还是虚树上的,同时以下都以插入为例。

如何在log时间内查询一个点最近的父亲?

处理出DFS序后,我们新建了一个点,那么对于这个这个新建的点,如果是叶子节点的,那么整个子树(实树)直接认为其是父亲(用线段树实现),但是如果是非叶子节点,可以发现,他建立时最多只有两个儿子(虚树)节点(因为我们只要两个点有了LCA(实树)就建),然后把DFS序分成两段即可,但是需要注意的是,不一定是两个儿子,有时候只有一个儿子,因为LCA可能是其自己。

如何在log的时间内查询一个点的某个儿子的子树内的儿子节点编号

首先一个点的一个儿子(原树)的子树内的只可能存在一个儿子(虚树),两个的话他们必然会产生一个LCA,那么怎么查到这个点就是重中之重的事了,由于实树儿子的编号是固定的,我们可以在这个点的平衡树中插入其儿子的编号,而附加权值就是这个儿子子树中的虚树儿子编号。

实现

由于$1$一直都在,所以$zans$表示到$1$点的距离,根据要不要经过$1$决定加还是不加。(本人觉得$root$的实现会更简单吧)

当然只有亿点细节。

时间复杂度:$O(nlogn)$,以及亿点点的常数,但也许是因为平衡树跑不满,或者因为正解用了set的缘故,我跑的竟然比正解快???

#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<ctime>
#define  N  110000
#define  M  210000
using  namespace  std;
typedef  long  long  LL;
//FHQ treap(平衡树)
int  val[M],ke1[M],ke2[M],tot,rt[M],siz[N],son[M][2];bool  li[N]/*这个点是否已经存在异象石*/;//最上层的点全部归到1 
void  spilt(int  now,int  k,int  &A,int  &B)
{
    if(!now)A=B=0;
    else
    {
        if(ke1[now]<=k)A=now,spilt(son[A][1],k,son[A][1],B);
        else  B=now,spilt(son[B][0],k,A,son[B][0]);
    }
}
int  mer(int  A,int  B)
{
    if(!A  ||  !B)return  A+B;
    if(val[A]<=val[B])son[A][1]=mer(son[A][1],B);
    else  son[B][0]=mer(A,son[B][0]),A^=B^=A^=B;
    return  A; 
}
inline  void  add(int  id,int  k1,int  k2)
{
    tot++;val[tot]=rand();ke1[tot]=k1;ke2[tot]=k2;
    int  x,y;spilt(rt[id],k1,x,y);
    rt[id]=mer(mer(x,tot),y);
}
inline  void  del(int  id,int  k)
{
    int  x,y,z;spilt(rt[id],k,x,z);spilt(x,k-1,x,y);
    rt[id]=mer(x,z);
}
inline  void  change(int  id,int  k1,int  k2)
{
    int  x,y,z;spilt(rt[id],k1,x,z);spilt(x,k1-1,x,y);
    ke2[y]=k2;
    rt[id]=mer(x,mer(y,z));
}
inline  int  findz(int  id,int  k)//这个子树是否存在虚树的儿子 
{
    int  bk=0;
    int  x,y,z;spilt(rt[id],k-1,x,y);spilt(y,k,y,z);
    if(y)bk=ke2[y];
    rt[id]=mer(mer(x,y),z);
    return  bk;
}
//线段树 
struct  TREE
{
    int  l,r,c;
}tr[M];int  tlen;
void  bt(int   l,int  r)
{
    int  now=++tlen;
    if(l<r)
    {
        int  mid=(l+r)>>1;
        tr[now].l=tlen+1;bt(l,mid);
        tr[now].r=tlen+1;bt(mid+1,r);
    }
    else  tr[now].c=1;
}
inline  void  set_c(int  now,int  k){tr[now].c=k;}
inline  void  downdate(int  now)
{
    if(tr[now].c)set_c(tr[now].l,tr[now].c),set_c(tr[now].r,tr[now].c),tr[now].c=0;
}
void  CHG(int  now,int  l,int  r,int  ll,int  rr,int  k)
{
    if(ll>rr)return  ;
    if(l==ll  &&  r==rr){set_c(now,k);return  ;}
    downdate(now);
    int  mid=(l+r)/2;
    if(rr<=mid)CHG(tr[now].l,l,mid,ll,rr,k);
    else  if(mid<ll)CHG(tr[now].r,mid+1,r,ll,rr,k);
    else  CHG(tr[now].l,l,mid,ll,mid,k),CHG(tr[now].r,mid+1,r,mid+1,rr,k);
}
int  findans(int  now,int  l,int  r,int  id)
{
    if(tr[now].c)return  tr[now].c;
    int  mid=(l+r)/2;
    if(id<=mid)return  findans(tr[now].l,l,mid,id);
    else  return  findans(tr[now].r,mid+1,r,id);
}
//边目录 
struct  node
{
    int  y,c,next;
}a[M];int  len,last[N];
inline  void  ins(int  x,int  y,int  c){len++;a[len].y=y;a[len].c=c;a[len].next=last[x];last[x]=len;}
//LCA
int  fa[N][20],top,be[N],ll[N],rr[N],dep[N];
LL  dis[N];
void  dfs(int  x)
{
    ++top;be[x]=top;ll[x]=top;
    for(int  i=1;i<=18;i++)
    {
        fa[x][i]=fa[fa[x][i-1]][i-1];
        if(!fa[x][i])break;
    }
    for(int  k=last[x];k;k=a[k].next)
    {
        int  y=a[k].y;
        if(y!=fa[x][0])dis[y]=dis[x]+a[k].c,dep[y]=dep[x]+1,fa[y][0]=x,dfs(y);
    }
    rr[x]=top;
}
int  lca(int  x,int  y)
{
    for(int  i=18;i>=0;i--)
    {
        if(dep[fa[x][i]]>dep[y])x=fa[x][i];
    }
    return  x;
}
int  lcac(int  x,int  y)
{
    if(dep[x]>dep[y])x^=y^=x^=y;
    for(int  i=18;i>=0;i--)
    {
        if(dep[fa[y][i]]>=dep[x])y=fa[y][i];
    }
    if(x==y)return  y;
    for(int  i=18;i>=0;i--)
    {
        if(fa[x][i]!=fa[y][i])x=fa[x][i],y=fa[y][i];
    }
    return  fa[x][0];
}
int  n,m;
LL  ans,zans/*表示连向1的点的距离,如果siz[1]>1则可以加入*/;
inline  void  del_dian(int  x,int  fat=0)//删除一个点,仅当这个点只有一个儿子的时候 
{
    if(li[x]  ||  x==1)return  ;//如果他只是单纯的自己一个点的话,或者说他是1的话,那没事了 
    if(!fat)fat=findans(1,1,n,be[fa[x][0]]);//找到x的父亲
    int  z=lca(x,fat),t=ke2[rt[x]]/*找到其唯一的一个节点*/;
    //删除x 
    del(x,ke1[rt[x]]);siz[x]=0;
    CHG(1,1,n,ll[x],ll[t]-1,fat);
    CHG(1,1,n,rr[t]+1,rr[x],fat);

    //插入 
    change(fat,z,t);

    if(fat==1)
    {
        ans-=dis[t]-dis[x];
        zans+=dis[t]-dis[x];
    }

}
int  main()
{
    srand(666);
    dep[0]=-1;
    scanf("%d",&n);
    for(int  i=1;i<n;i++)
    {
        int  x,y,c;scanf("%d%d%d",&x,&y,&c);
        ins(x,y,c);ins(y,x,c);
    }
    dfs(1);
    scanf("%d",&m);
    bt(1,n);
    for(int  i=1;i<=m;i++)
    {
        char  st[10];scanf("%s",st);
        if(st[0]=='+')
        {
            int  x;scanf("%d",&x);
            if(!li[x])//插入点 
            {
                li[x]=1;siz[x]++;//他本身自己就是一个点 
                int  y=findans(1,1,n,be[x])/*表示父亲节点*/;
                if(x!=y)
                {
                    int  z=lca(x,y)/*y的下面*/,t/*和x结合的点*/;
                    if((t=findz(y,z)))//什么,有点可以结合 
                    {
                        //先把x,t插入到k中 
                        int  k=lcac(t,x);//新建立一个点代表他们两个
                        int  shit;
                        if(k!=x)shit=lca(x,k),add(k,shit,x);//自己怎么能加入自己呢? 
                        shit=lca(t,k),add(k,shit,t);//t肯定不等于k,否则x的父亲就是t了 
                        siz[k]=2;//有两个点 
                        CHG(1,1,n,ll[k],ll[t]-1,k);//你们的父亲都是我 
                        CHG(1,1,n,rr[t]+1,rr[k],k);//你们的父亲都是我 
                        //此时的k已经可以等效x,t了 
                        change(y,z,k);//将原本t的位置改成k 
                        if(y==1)
                        {
                            ans+=dis[t]+dis[x]-2*dis[k];
                            zans+=dis[k]-dis[t];
                        }
                        else  ans+=dis[x]-dis[k];
                        if(k!=x)CHG(1,1,n,ll[x],rr[x],x);
                    }
                    else
                    {
                        add(y,z,x),siz[y]++;//没有就加入 
                        if(y!=1)ans+=dis[x]-dis[y];
                        else  zans+=dis[x]-dis[y];
                        CHG(1,1,n,ll[x],rr[x],x);
                    }
                }
            }
        }
        else  if(st[0]=='-')
        {
            int  x;scanf("%d",&x);
            if(li[x])//插入点 
            {
                int  y=findans(1,1,n,be[fa[x][0]])/*表示父亲节点*/;
                li[x]=0;siz[x]--;
                if(!siz[x])//只有一个点 
                {
                    CHG(1,1,n,ll[x],rr[x],y);
                    int  z=lca(x,y);del(y,z);siz[y]--;
                    if(y==1)zans-=dis[x];
                    else  ans-=dis[x]-dis[y];
                    if(siz[y]==1)del_dian(y);
                }
                else  if(siz[x]==1)del_dian(x,y);//只剩下子树中的一个点,破坏掉这个原有的结构 
            }
        }
        else
        {
            printf("%lld\n",ans+zans*(siz[1]>1));
        }
    }
    return  0;
}

正解

先求出树上点的DFS序,将异象石按DFS序排序,连成一个环,然后将相邻两个异象石距离相加,得到的就是答案的两倍。

严谨参照 https://www.cnblogs.com/2aptx4869/p/13513541.html (虽然我并不知道为什么他还要枚举$a_3$和$a_2$在树上的相对位置)

但是我的证明是,将其像我的做法一样处理(但是$1$不是严格存在了,严格存在只是因为代码难处理)

然后得到了一棵虚树,不难想到一定存在一种遍历方案,使得实树中按异象石的DFS排列后的异象石序列,和虚树中按异象石的DFS排列的异象石序列相同。(简单来说就是在虚树中遍历跟在实树中遍历是一样的,所以这个证明放到实树遍历一样的,虚树更加直观)。

接下来我会证明,这个加法的过程,其实就是$DFS$遍历中进入和回溯时经过的边的权值的总和。

对于一个实点而言,你在遍历的过程中不管是回溯还是进入,你遍历到的下一个实点,就是你DFS序的后一位,而进入回溯所记录的边的总和,就是你们两个的距离(否则中间必然存在其他实点,因为叶子节点都是实点)。

不过刚开始从根节点走到$1$ 号实点以及$n$号实点回溯到根节点记录的边权,你可以认为加起来是$n$号实点在找$1$号实点。

同时这个虚树所有边的权值就是答案,而DFS所记录的边权其实就是所有边权值和的两倍。

证毕。

至于维护DFS序的排序,用的是set。

代码也是抄的QMQ。

时间复杂度:$O(nlogn)$

#include <bits/stdc++.h>
#define all(n) (n).begin(), (n).end()
#define se second
#define fi first
#define pb push_back
#define mp make_pair
#define sqr(n) (n)*(n)
#define rep(i,a,b) for(int i=(a);i<=(b);++i)
#define per(i,a,b) for(int i=(a);i>=(b);--i)
#define IO ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr)
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
typedef pair<ll, ll> PLL;
typedef vector<int> VI;
typedef double db;

const int N = 1e5 + 5;

int n, m, _, k;
int h[N], ne[N << 1], to[N << 1], co[N << 1], tot;
int dfn[N], cnt, d[N], f[N][30], t;
ll dist[N], ans;
char s[3];
set<PII> st;

void add(int u, int v, int c) {
    ne[++tot] = h[u]; h[u] = tot; to[tot] = v; co[tot] = c;
}

void bfs(int s) {
    queue<int> q;
    q.push(s); d[s] = 1; dist[s] = 0;
    rep (i, 0, t) f[s][i] = 0;

    while (!q.empty()) {
        int x = q.front(); q.pop();
        for (int i = h[x]; i; i = ne[i]) {
            int y = to[i];
            if (d[y]) continue;
            d[y] = d[x] + 1;
            dist[y] = dist[x] + co[i];
            f[y][0] = x;

            for (int j = 1; j <= t; ++j) 
                f[y][j] = f[f[y][j - 1]][j - 1];

            q.push(y);
        }
    }
}

int lca(int x, int y) {
    if (d[x] > d[y]) swap(x, y);
    per (i, t, 0) 
        if (d[f[y][i]] >= d[x]) y = f[y][i];

    if (x == y) return x;

    per (i, t, 0)
        if (f[x][i] != f[y][i]) x = f[x][i], y = f[y][i];

    return f[x][0]; 
}

void dfs(int u) {
    dfn[u] = ++cnt;
    for (int i = h[u]; i; i = ne[i]) {
        int y = to[i];
        if (dfn[y]) continue;
        dfs(y);
    }
}

void worka() {
    auto it = st.upper_bound({ dfn[k], k });
    int x, y;
    if (it == st.begin() || it == st.end()) x = st.begin()->se, y = st.rbegin()->se;
    else  x = it->se, y = (--it)->se;

    ans += (dist[k] << 1) - ((dist[lca(k, x)] + dist[lca(k, y)] - dist[lca(x, y)]) << 1);
    st.insert({ dfn[k], k });
}

void workb() {
    if (st.size() == 1) { st.clear(); return; }

    auto it = st.lower_bound({ dfn[k], k }), ita = it; ++ita;
    int x, y;
    if (ita == st.end()) y = st.begin()->se;
    else y = ita->se;
    if (it == st.begin()) x = st.rbegin()->se;
    else x = (--it)->se;

    ans -= (dist[k] << 1) - ((dist[lca(k, x)] + dist[lca(k, y)] - dist[lca(x, y)]) << 1);
    st.erase(--ita);
}

int main() {
    IO; cin >> n;
    rep(i, 2, n) {
        int u, v, c; cin >> u >> v >> c;
        add(u, v, c); add(v, u, c);
    }

    t = log2(n - 1) + 1;
    dfs(1); bfs(1);

    cin >> m;
    rep(i, 1, m) {
        cin >> s;
        if (s[0] == '?') cout << (ans >> 1) << '\n';
        else {
            cin >> k;
            if (st.empty()) st.insert({ dfn[k], k });
            else if (s[0] == '+') worka();
            else workb();
        }
    }
    return 0;
}




题目

题目

做法

首先,我们不难证明当K=2时,一定存在一种最小方案使得两个环之间不存在边的交集的。(但是需要注意,有交集不一定代表不是最优解,说不定是因为有交集但是选取了更大区域的边)

至于证明,看这张图:

在这里插入图片描述
第一张图表示重复部分可以通过上移解决,同时减少了所需距离,第二个图表示两个重复部分可以通过连接不同的边办到相同的距离来解决重复。
在这里插入图片描述
至于严谨的证明,你可以像这个图一样画两个圆,然后枚举这两个连接上去的边的位置进行分类讨论,就可以发现这个是对的了,但是需要注意的是,两个圆的重复部分只可能是连续的一段(单个点也算),如果是交集部分是两个部分的话,你可以发现无法通过切割两条边使得它变成一棵树。.

然后随随便便跑个树形DP就行了。

$f[x][0/1][0/1/2]$表示在$x$这个点是否正在未成形的环上,同时子树中已经有了几个成型的环时,环上的边的最大值。(因为我预处理走过所有边的总和,减去环上的边的距离)。

时间复杂度:$O(n)$

//这鬼畜的转移
#include<cstdio>
#include<cstring>
#define  N  110000
#define  M  210000
using  namespace  std;
inline  int  mymax(int  x,int  y){return  x>y?x:y;}
struct  node
{
    int  y,next;
}a[M];int  len,last[N];
inline  void  ins(int  x,int  y){len++;a[len].y=y;a[len].next=last[x];last[x]=len;}
int  f[N][2][3];//表示第i个点目前是否有圈,已经完成了k个圈的最大代价
int  n,ans=0,K;
void  dfs(int  x,int  fa)
{
    f[x][0][2]=f[x][0][1]=f[x][1][1]=-999999999;
    for(int  k=last[x];k;k=a[k].next)
    {
        int  y=a[k].y;
        if(y!=fa)
        {
            dfs(y,x);
            if(K==1)
            {
                f[x][0][1]=mymax(mymax(f[y][1][0]+f[x][1][0]+1,f[y][0][1]),f[x][0][1]);
                f[x][1][0]=mymax(f[y][1][0]+1,f[x][1][0]);
            }
            else
            {
                f[x][0][2]=mymax(mymax(mymax(f[y][1][1]+f[x][1][0]+1,f[y][1][0]+f[x][1][1]+1),f[y][0][2]),mymax(f[x][0][2],f[x][0][1]+f[y][0][1]));
                f[x][1][1]=mymax(mymax(f[x][1][1],mymax(f[y][1][1]+1,f[y][1][0]+f[x][0][1]+1)),f[y][0][1]+f[x][1][0]);
                f[x][0][1]=mymax(mymax(f[y][1][0]+f[x][1][0]+1,f[y][0][1]),f[x][0][1]);
                f[x][1][0]=mymax(f[y][1][0]+1,f[x][1][0]);
            }
        }
    }
    f[x][1][1]=mymax(f[x][0][1],f[x][1][1]);
}
int  main()
{
    scanf("%d%d",&n,&K);ans=2*(n-1)+K;//表示最多走这么多边,后面会减的 
    for(int  i=1;i<n;i++)
    {
        int  x,y;scanf("%d%d",&x,&y);
        ins(x,y);ins(y,x);
    }
    dfs(1,0);
    printf("%d\n",ans-f[1][0][K]);
    return  0;
}



题目

题目

做法

目前看下来貌似我的做法的复杂度是比较优秀,是$O(n^3)$

当然,$n=101$,首先,点的个数最多是边的个数加一,这个很好理解。

我们开始思考,走这么多边,肯定是要走环的,对吧,那么有一个假想,如果他就是在一条最短路上的最小边反复横跳呢?

我们用“表面否的算法”(Bellman - Ford算法)处理起点和终点到达各个点在走过$k$条边时的最短路,当然$k$最大为多少呢?,我们假定这条路径就在这里反复横跳,不存在其余的环,那么$k$最大就为点的个数,但是,其实是有可能存在其他环的,因为我们这样来回弹跳,只会造成偶数环,那么如果刚好找个奇数环走一遍,然后改变所需要的边数能让答案更小呢,所以$k$要是最大点数的两倍。当然,至于两个环或者一个偶数环的存在,你都可以把环去掉改成左右横跳,权值更小,但是由于我们很难知道这个边是不是路径上最小的边,所以我们需要假定他是,然后枚举所有的边就行了。

#include<cstdio>
#include<cstring>
#define  N  110
#define  NN  1100
#define  M  210
using  namespace  std;
template<class  T>
inline  T  mymin(T  x,T  y){return  x<y?x:y;}
class  EDGE
{
    public:
        struct  node
        {
            int  y,c,next;
        }a[M];int  len,last[NN];
        void  ins(int  x,int  y,int  c)
        {
            len++;a[len].y=y;a[len].c=c;a[len].next=last[x];last[x]=len;
        }
}a1,a2;
struct  FUCKKK
{
    int  x,y,c;
}fuck[N];
int  f1[M][N],f2[M][N];int  n,m,st,ed;bool  v[N];
int  be[NN],cnt,sta[N];
void  dfs(int  x)
{
    for(int  k=a1.last[x];k;k=a1.a[k].next)
    {
        int  y=a1.a[k].y;
        if(!be[y])
        {
            be[y]=++cnt;sta[cnt]=y;
            dfs(y);
        }
        a2.ins(be[x],be[y],a1.a[k].c);
    }
}
int  main()
{
    scanf("%d%d%d%d",&n,&m,&st,&ed);
    for(int  i=1;i<=m;i++)
    {
        int  c,x,y;scanf("%d%d%d",&c,&x,&y);
        a1.ins(x,y,c);a1.ins(y,x,c);
        fuck[i].x=x;fuck[i].y=y;fuck[i].c=c;
    }
    sta[cnt=1]=st;be[st]=1;
    dfs(st);
    //处理和st,ed相通的点的个数
    memset(f1,30,sizeof(f1));
    memset(f2,30,sizeof(f2));
    f1[0][1]=f2[0][be[ed]]=0;
    int  limit=a2.len;
    for(int  i=0;i<limit;i++)
    {
        for(int  j=1;j<=cnt;j++)
        {
            for(int  k=a2.last[j];k;k=a2.a[k].next)
            {
                int  y=a2.a[k].y;
                f1[i+1][y]=mymin(f1[i+1][y],f1[i][j]+a2.a[k].c);
                f2[i+1][y]=mymin(f2[i+1][y],f2[i][j]+a2.a[k].c);
            }
        }
    }
    //Bellman - Ford
    int  ans=999999999;
    for(int  i=1;i<=m;i++)
    {
        if(!be[fuck[i].x])continue;
        int  x=be[fuck[i].x],y=be[fuck[i].y];
        int  ed1=mymin(limit,n);
        for(int  j=0;j<=ed1;j++)
        {
            int  ed2=mymin(limit,n-j);
            for(int  k=0;k<=ed2;k++)
            {
                if((n-j-k)&1)
                {
                    int  shit=(int)(n-j-k)*fuck[i].c;
                    ans=mymin(mymin(f1[j][x]+f2[k][y],f1[j][y]+f2[k][x])+shit,ans);
                }
                else
                {
                    int  shit=(int)(n-j-k)*fuck[i].c;
                    ans=mymin(mymin(f1[j][x]+f2[k][x],f1[j][y]+f2[k][y])+shit,ans);
                }
            }
        }
    }
    printf("%d\n",ans);
    return 0;
}

当然,常数稍稍大了点,但是无所谓啦。

最后的最后,安利一下自己的博客QMQ: https://blog.csdn.net/zhangjianjunab

如果不给安利我会撤下来的




其实这个人是站在第n个围栏上面,还要跨过第n个围栏,并不可以直接忽略第n个围栏




RT




RT




这个人不能再山上停留,要一直不间断地走




RT,建议开Ofast




题目

题目

题解

什么鬼,我竟然用莫比乌斯反演做出来了?!?!?!?!

咳咳,讲讲怎么做吧,设$f$为莫比乌斯函数,那么就有:

$\sum\limits_{k|n}^nk\sum\limits_{i|\frac{n}{k}}^{\frac{n}{k}}\frac{n}{ki}f(i)$

$\sum\limits_{k|n}^n\sum\limits_{i|\frac{n}{k}}^{\frac{n}{k}}\frac{n}{i}f(i)$

设$z=ki$

那么就有

$\sum\limits_{z|n}^n\sum\limits_{i|z}^{z}\frac{n}{i}f(i)$

$\sum\limits_{i|n}^n\frac{n}{i}f(i)\sum\limits_{i|z,z|n}^{n}$

根据$f$的的性质,不难想出我们只需要枚举质因子不重复的$i$,然后对于每个$i$统计$\sum\limits_{i|z,z|n}^{n}$即可。

因为最多$9$个不同的质因子,所以时间复杂度是:$O(2^9+\sqrt{n})$。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath> 
#define  N  51000
using  namespace  std;
typedef  long  long  LL;
LL  a[N],b[N],to1;//表示因子
LL  n;
int  v;
void  fenjie(LL  x)//分解质因子
{
    LL  y=sqrt(x);
    for(LL  i=2;i<=y  &&  i<=x;i++)
    {
        if(x%i==0)
        {
            LL  t=0;
            while(x%i==0)x/=i,t++;
            a[++to1]=i;b[to1]=t;
        }
    }
    if(x>1)a[++to1]=x,b[to1]=1;
}
int  main()
{
    scanf("%lld",&n);
    fenjie(n);
    int  limit=(1<<to1)-1;
    LL  ans=0;
    for(int  i=0;i<=limit;i++)
    {
        LL  x=1,y=1;int  z=0;
        for(int  j=1;j<=to1;j++)
        {
            if(i&(1<<(j-1)))
            {
                z++;
                x*=a[j];//有这个数字 
                y*=b[j];//统计 
            }
            else  y*=(b[j]+1);
        }
        LL  f=1;
        if(z&1)f=-1;
        ans+=(n/x)*f*y;//统计个数
    }
    printf("%lld\n",ans);
    return  0;
}



999911657 999911659

这组数据,因为指数会变成0,所以乘方会变成1,但是答案是0