51nod 约数和(数论)

题目链接：

约数和

基准时间限制：2 秒空间限制：131072 KB 分值: 80

有三个下标从1到n的数组a、b、c。

a数组初始全为0。

b[i]=∑j|ia[j]

c[i]=∑j|ib[j]

需要进行下列操作：

1 x y :将a[x]加上y

2 x :询问当前c[x]的值

j | i 表示j是i的约数。

Input

第一行两个整数，n和q，分别表示数组下标范围和操作次数。（1<=n,q<=1,000,000）

接下来q行，描述一个操作。(x随机,1<=x<=n,1<=y<=10^6)

Output

对于每一个第二种操作输出一个答案。

Input示例

Output示例

4

8

6

题意：

思路：

每次a[x]+y,对c[i]的影响是这样的:
c[i]+=y*f[x/i];
其中i|x   f[x]表示x的约数的个数;
为什么是这样呢？
我来举个例子：比如a[2]+y,c[12]+y*f[12/2]=c[12]+y*f[6],  a[2]变化,导致b[2],b[4],b[6],b[8],b[10],b[12],....都要加y,而其中对c[12]有影响的是b[2],b[4],b[6],b[12],除2就是1,2,3,6这些就是f[6]啦,就是这样的啦;
x随机,那么就可以logn  修改c[i]了;

开了输入和输出挂,快了好多好多;挂是我在bc的代码上从一个大神的代码上搞下来的,好羞耻（捂脸

AC代码：

//#include <bits/stdc++.h>

#include <vector>

#include <iostream>

#include <queue>

#include <cmath>

#include <map>

#include <cstring>

#include <algorithm>

#include <cstdio>

using namespace std;

#define Riep(n) for(int i=1;i<=n;i++)

#define Riop(n) for(int i=0;i<n;i++)

#define Rjep(n) for(int j=1;j<=n;j++)

#define Rjop(n) for(int j=0;j<n;j++)

#define mst(ss,b) memset(ss,b,sizeof(ss));

typedef long long LL;

template<class T> void read(T&num) {

    char CH; bool F=false;

    for(CH=getchar();CH<''||CH>'';F= CH=='-',CH=getchar());

    for(num=;CH>=''&&CH<='';num=num*+CH-'',CH=getchar());

    F && (num=-num);

}

int stk[], tp;

template<class T> inline void print(T p) {

    if(!p) { puts(""); return; }

    while(p) stk[++ tp] = p%, p/=;

    while(tp) putchar(stk[tp--] + '');

    putchar('\n');

}

const LL mod=1e9+;

const double PI=acos(-1.0);

const LL inf=1e18;

const int N=1e6+;

int n,q;

LL c[N],f[N];

void Init()

{

    for(int i=;i<N;i++)

    {

        for(int j=;j*i<N;j++)

        {

            f[i*j]++;

        }

    }

}

int main()

{

      read(n);read(q);

      Init();

      int flag,x,y;

      while(q--)

      {

          read(flag);

          if(flag==)

          {

              read(x);read(y);

              for(int i=; ;i++)

              {

                  int p=i*x;

                  if(p>=N)break;

                  c[p]=c[p]+f[i]*y;

              }

          }

          else read(x),print(c[x]);

      }

    return ;

}

秒客网

51nod 约数和(数论)

相关文章