DAY2 总结

技术文章 6个月前 完美者
1,324 0

标签:==   typedef   思考   lld   注意   计算   inf   prim   res   

知识的迁移,题目意思的分析

T1:互质数对

技术图片

 

 显然,对于在线的题目,我们应该认真的思考(如果计算过于麻烦,我们是不是可以通过增量来计算

推导过程:技术图片

 

 第二步到第三步:因为每一个d要满足|ax和ay,所以对于每一个μ来说,只有对于每一个ax加入进来的约数,会产生的只有(ay中是d倍数的个数,记录并计算就可

注意数据范围 我们要统计约数,所以说数组的大小是数值范围而不是n,同样给我们以启示

如果说数论题目值域范围不大,就可以考虑用枚举约数的方式求解

#include <stdio.h>
#include <algorithm>
#include <cstring>
#include <vector>

using namespace std;

const int maxn=2000020;
typedef long long ll;
int a[maxn];
bool c[maxn],st[maxn];
int prime[maxn],mob[maxn],cnt,f[maxn];
int n,q;
ll ans=0;
vector<int> v[maxn];

inline void init(int k)
{
    mob[1]=1;
    for(int i=2;i<=k;i++)
    {
        if(!st[i])
        {
            prime[cnt++]=i;
            mob[i]=-1;
        }
        for(int j=0;prime[j]*i<=k&&j<cnt;j++)
        {
            st[prime[j]*i]=true;
            if(i%prime[j]==0) break;
            mob[prime[j]*i]=-mob[i];
        }
    }
    for(int i=1;i<=k;i++)
    if(mob[i]!=0)// ó??ˉ 
        for(int j=i;j<=k;j+=i)
        {
            v[j].push_back(i);//±£′?μ??1ê???êy°? 
        }
    return ;
}

int clar(int x)
{
    int res=0;
    for(int i=0;i<v[x].size();i++)
    {
        res+=mob[v[x][i]]*f[v[x][i]];
    }
    return res;
}
void ins(int x)
{
    ans+=clar(x);
    for(int i=0;i<v[x].size();i++)
    {
        f[v[x][i]]++;
    }
    return;
    
}
void del(int x)
{    
    
    for(int i=0;i<v[x].size();i++)
    {
        f[v[x][i]]--;
    }
    ans-=clar(x);
    return;
}
int main()
{
//    freopen("pair.in","r",stdin);
//    freopen("pair.out","w",stdout);
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    init(500020);
    while(q--)
    {
        int x;scanf("%d",&x);
        if(!c[x]) ins(a[x]);    
        else del(a[x]);
        c[x]^=1;
        printf("%lld\n",ans);
    }
    return 0;
}

 

DAY2 总结

标签:==   typedef   思考   lld   注意   计算   inf   prim   res   

原文地址:https://www.cnblogs.com/ILHYJ/p/13902384.html

版权声明:完美者 发表于 2020-10-31 2:00:49。
转载请注明:DAY2 总结 | 完美导航

暂无评论

暂无评论...