EC Final 重现赛 M - value 二进制枚举

题目大意：
有一个集合A={1,2....n}，从A中选出一个子集，在这个子集中 初始权值为 ,对于任意的i>=2,j>=2，如果有 ,那么这个子集的权值就要减去 。
题目思路

嗯..刚开始思路是对的..

• 第一步：可以确定我们可以按幂去分组，因为2的幂与3的幂集合之间没有任何的交集，也就是说，如果已经把2选入到子集中，那么3选进去与3不选进去是没有影响的。能产生的影响的只有 底数相同的幂。

• 第二步：我们按幂分组之后，组内的数就被确定，之后我们就需要枚举组内的数可以产生的组合，然后分别去修改这些组合，使得这些组合满足题目中的条件。最后计算当前这种组合的权值，作为这个子集这时的权值，枚举所有组合的权值之后取一个最大值，即为幂分组后该组对答案的贡献。

• 第三步:如何计算出当前这个组合的权值呢？题目中说只要出现一对(i,j)满足那么bj就要减去一次，所以我们首先令当前组合的ai全部加入，第一层for循环枚举x，第二层for循环枚举y是不是x的幂。如果是的话就减去一次：

  ll judge(ll x,ll y)
  {
    for(ll k=x;k<=n;k*=x)
        if(k==y) return 1;
    return 0;
  }
  //以上为judge函数，判断y是否为x的幂。
        for(ll k=1;k<=x;k++)
        {
  
            if(i>>(k-1)&1)//第k位是否为1
                c[++cot]=save[k];
        }
        for(ll k=1;k<=cot;k++) sum+=a[c[k]];
        for(ll k=1;k<=cot;k++)
        {
            for(ll j=1;j<=cot;j++)
            {
                if(c[j]<c[k]&&judge(c[j],c[k]))
                    sum-=b[c[k]];
            }
        }

• 第四步: 计算一下时间复杂度，因为二进制枚举的时间复杂度为: ,指数级别的复杂度是很令人害怕的，开始我也没敢写，不过计算一下这个复杂度：按幂分组之后，组中元素个数最多为 ,也就是最坏的二进制枚举为 ,然后外层套一个sqrt(N)，因为sqrt(N)之后的，要么已经被幂分组分进去了，要么没有被幂分组分进去，此时这个数可以直接加入到这个子集里。所以总体的时间复杂度为： ,由于n是100000大概是个1e7~5e7的复杂度，但是绝对比这个复杂度要小很多，因为计算的最坏情况！

  
  
  所以剩下的内容就看你的二进制枚举学的怎么样了，其实感觉挺简单的，开始M题意读错了，唉.. 放一下代码啦
  hhaha 牛哥会在阿楚姐的帮助下送我抱枕嘛？

ll n,m,p;
ll a[maxn],b[maxn],c[maxn];
ll vis[maxn];
ll save[maxn];
ll judge(ll x,ll y)
{
    for(ll k=x;k<=n;k*=x)
        if(k==y) return 1;
    return 0;
}
ll work(ll x)
{
    ll maxl=0;
    for(ll i=0;i<(1<<x);i++)
    {
        ll cot=0;
        ll sum=0;
        for(ll k=1;k<=x;k++)
        {

            if(i>>(k-1)&1)//第k位是否为1
                c[++cot]=save[k];
        }
        for(ll k=1;k<=cot;k++) sum+=a[c[k]];
        for(ll k=1;k<=cot;k++)
        {
            for(ll j=1;j<=cot;j++)
            {
                if(c[j]<c[k]&&judge(c[j],c[k]))
                    sum-=b[c[k]];
            }
        }
        maxl=max(sum,maxl);
    }
    return maxl;
}
int main()
{
    scanf("%lld",&n);
    for(ll i=1;i<=n;i++) scanf("%lld",&a[i]);
    for(ll i=1;i<=n;i++) scanf("%lld",&b[i]);
    ll res=a[1];
    for(ll i=2;i*i<=n;i++)
        if(!vis[i])
        {
            for(ll k=i*i;k<=n;k*=i)
                vis[k]=1;
        }
    for(ll i=2;i<=n;i++)
    {
        ll cnt=0;
        if(i*i<=n&&!vis[i])
        {
            for(ll k=i;k<=n;k*=i) save[++cnt]=k;
            res+=work(cnt);
        }
        else if(i*i>n&&!vis[i]) res+=a[i];
    }
    printf("%lld\n",res);
    return 0;
}