洛谷 P1483 序列变换

https://www.luogu.org/problemnew/show/P1483

数据范围不是太大。

一个数组记录给k，记录每个数加了多少。

对于查询每个数的大小，那么就枚举每个数的因子，加上这个每个因子假的数。

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
using namespace std;
#define LL long long
LL n,m,k,a[1000006],f[1000006];
LL x,y,z;
LL work(LL x)
{
    LL ans=a[x];
    for(LL i=1;i*i<=x;i++)
    {
        if(x%i==0)
        {
            if(i*i==x)ans+=f[i];
            else ans+=f[i]+f[x/i];
        }
    }
    return ans;
}
int main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    for(int i=1;i<=m;i++)
    {
        scanf("%lld",&z);
        if(z==1)
        {
            scanf("%lld%lld",&x,&y);
            f[x]+=(LL)y;
        }
        if(z==2)
        {
            scanf("%lld",&x);
            printf("%lld
",work(x));
        }
    }
}

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <queue>
using namespace std;
#define LL long long
LL n,m,k,a[1000006],f[1000006];
LL x,y,z;
LL work(LL x)
{
    LL ans=a[x];
    for(LL i=1;i*i<=x;i++)
    {
        if(x%i==0)
        {
            if(i*i==x)ans+=f[i];
            else ans+=f[i]+f[x/i];
        }
    }
    return ans;
}
int main()
{
    scanf("%lld%lld",&n,&m);
    for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
    for(int i=1;i<=m;i++)
    {
        scanf("%lld",&z);
        if(z==1)
        {
            scanf("%lld%lld",&x,&y);
            f[x]+=(LL)y;
        }
        if(z==2)
        {
            scanf("%lld",&x);
            printf("%lld
",work(x));
        }
    }
}