题解 P1483 【序列变换】

· · 题解

一开始以为用线段树之类的去写。然后发现不用这么麻烦！！！（标签）

写题就是爆~ 得了个60！仔细看了下数据范围 发现操作二不超过10000。我们就直接把题目说的a k的倍数加上x转换一下不就是ok了吗！

y是x的倍数 也可以说x是y的约数。比如（6是2的倍数，那么2就是6的约数咯）。那我们直接把一操作的位置和值存起来。需要的时候在找是不是我这个数的约数。如果是就加上不是则跳过就ok了。

#include<bits/stdc++.h>
using namespace std;
const int ch=1000010;
int a[ch],n,m,ans;
map<int,int>t;
int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    while(m--)
    {
        int x;
        scanf("%d",&x);
        if(x==1)
        {
            int y,z;
            scanf("%d%d",&y,&z);
            t[y]+=z;//标记起来 
        }
        if(x==2)
        {
            int z,zhi=0;
            scanf("%d",&z);
            for(int i=1;i<=z/i;i++)//快速判断约数 
            {
                if(z%i==0)//如果这个数的约数 
                {
                    if(t[i]){zhi+=t[i];}//且出现过不为0就累加 
                    if(i!=z/i&&t[z/i])zhi+=t[z/i];//同上 
                }
            }
            printf("%d\n",a[z]+zhi);//原来的值加上增加的值 
        }
    }
}