#include<bits/stdc++.h> using namespace std; typedef long long ll; const ll inf=0x3f3f3f3f; int cnt=1;//边的数量 int head[110],cur[110];//head记录每一个点最后一条边的编号，cur记录当前点循环到了哪一条边 int n,deep[110],s,t,start;//s设为不选，t为选，即源点和汇点 //权值为负的点向s连容量为-w的边，权值为正的点向t连容量为w的边 //这里的容量相当于是割掉这条边的代价 ll ans,tmp; queue<int>q;//定义一个bfs寻找分层图时的队列 struct node { int to,next;//to即每一条边指向的点，next指向对应点的前一条边 ll w;//每一条边的残量 }num[25000]; void add(int start,int y,ll w)//对于所有有倍数关系的点，小的向大的连inf的边 //ans一开始为所有正权边的权值和 { num[++cnt].to=y; num[cnt].next=head[start]; num[cnt].w=w; head[start]=cnt; num[++cnt].to=start; num[cnt].next=head[y]; num[cnt].w=0; head[y]=cnt; } int bfs() { memset(deep,0,sizeof(deep));//初始化深度为0 deep[s]=1;//源点深度为1 q.push(s); while(!q.empty()) { int now=q.front(); q.pop(); for(int i=head[now];i;i=num[i].next) { if(!deep[num[i].to]&&num[i].w)//当前还未分配深度且残量不为零，则分配深度并放入队列 { deep[num[i].to]=deep[now]+1;//计算深度 q.push(num[i].to);//入队一个节点 } } } return deep[t]; } ll dfs(int start,ll minf)//当前节点，当前流量 { ll tmp=minf; if(start==t)//到达汇点直接返回前面流过来的流量 return minf; for(int &i=cur[start];i&&tmp;i=num[i].next)//当前弧优化，运用指针在修改i的同时，将cur[start]顺便修改 { if(deep[start]+1==deep[num[i].to]&&num[i].w)//满足分层图的性质 { ll t=dfs(num[i].to,min(num[i].w,tmp));//继续找增广路 tmp-=t;//剩余容量 num[i].w-=t;//正向边减 num[i^1].w+=t;//反向边加 } } return minf-tmp;//返回最小割 } void dinic() { while(bfs()) { memcpy(cur,head,sizeof(head));//每一次建立完分层图后都要把cur置为每一个点的第一条边 while(tmp=dfs(s,inf)) ans-=tmp;//减去最小割 } }
int main() { scanf("%d",&n); s=n+1; t=s+1; for(int i=1;i<=n;i++) { scanf("%d",&start); if(start>=0) { add(i,t,start); ans+=start; } else add(s,i,-start); } for(int i=1;i<=n;i++) { for(int j=2*i;j<=n;j+=i) { add(i,j,inf); } } dinic(); printf("%lld\n",ans); return 0; } /*最小割建模 最大流模板 dinic当前弧优化算法（isap 建模方法：分为选和不选两部分点， 把边的容量设为代价， 通过正负的约束来使得要求的是最小割， ans一开始统计全部保留和t点（保留点）连边的价值和*/