题目大意

　　有一个长度为 \(n\) 的序列。

　　有 \(m\) 次修改，每次给你 \(x,y\)，令 \(\forall 1\leq i\leq \lfloor\frac{n}{x}\rfloor,a_{ix}=a_{ix}+iy\)

　　还有 \(q\) 次询问，每次给你 \(x\)，求 \(\sum_{i=1}^{\lfloor\frac{n}{x}\rfloor}ia_{ix}\)

　　对 \(998244353\) 取模。

　　\(n\leq {10}^9,m,q\leq 200000\)，记 \(z\) 为所有 \(x\) 的 \(\operatorname{lcm}\)，那么 \(z\) 的质因子个数 \(w\) 不超过 \(10\)

题解

　　首先你要会 \(O(n\log\log n)\) 求高维前缀和&后缀和，这样就可以拿到 \(65\) 分。

　　容易发现，所有 \(z\) 的不超过 \(n\) 的因子个数 \(s\leq 200000\)。

　　因为所有修改&询问的数都是 \(z\) 的因子，所以可以把那些不是 \(z\) 的因子的位置的贡献放在那个数和 \(z\) 的 \(\gcd\) 处统计。

　　具体来说，我们在求高维前缀和的时候只求 \(z\) 的不超过 \(n\) 的因子的答案，求完之后把每个位置 \(x\) 的值乘上一个系数 \(f(\frac{n}{x})\) 。

\[ f(n)=\sum_{i=1}^ni^2[\gcd(i,z)=1] \]

　　\(f\) 可以筛出来。

　　高维后缀和也可以用类似的方法做。

　　然后就能得到答案了。

　　时间复杂度：\(O(w(s+\sqrt{n}))\)

代码

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             //using namespace std;typedef long long ll;typedef unsigned long long ull;typedef std::pair
             
               pii;typedef std::pair
              
                pll;void open(const char *s){#ifndef ONLINE_JUDGE char str[100];sprintf(str,"%s.in",s);freopen(str,"r",stdin);sprintf(str,"%s.out",s);freopen(str,"w",stdout);#endif}int rd(){int s=0,c,b=0;while(((c=getchar())<'0'||c>'9')&&c!='-');if(c=='-'){c=getchar();b=1;}do{s=s*10+c-'0';}while((c=getchar())>='0'&&c<='9');return b?-s:s;}void put(int x){if(!x){putchar('0');return;}static int c[20];int t=0;while(x){c[++t]=x%10;x/=10;}while(t)putchar(c[t--]+'0');}int upmin(int &a,int b){if(b
               
                a){a=b;return 1;}return 0;}const ll p=998244353;ll fp(ll a,ll b){ ll s=1; for(;b;b>>=1,a=a*a%p) if(b&1) s=s*a%p; return s;}const ll inv6=fp(6,p-2);std::tr1::unordered_map
                
                  s;//int s[10000010];int c[100010];int cnt;int a[200010];int tot;int ax[200010],ay[200010],bx[200010];int n,m,q;void dfs(int x,int y,int b){ if(b) a[++tot]=x; if((ll)x*c[y]<=n) dfs(x*c[y],y,1); if(y
                 
                  =1;j--) f1[j]=(f1[j]-x*f1[j/c[i]])%p; }}ll query(int x){ return x<=100000?f1[x]:f2[n/x];}int main(){ open("loj561"); scanf("%d%d%d",&n,&m,&q); for(int i=1;i<=m;i++) { scanf("%d%d",&ax[i],&ay[i]); s[ax[i]]=(s[ax[i]]+ay[i])%p; int x=ax[i]; for(int j=1;j<=cnt;j++) while(x%c[j]==0) x/=c[j]; for(int j=2;j*j<=x;j++) if(x%j==0) { c[++cnt]=j; while(x%j==0) x/=j; } if(x!=1) c[++cnt]=x; } for(int i=1;i<=q;i++) { scanf("%d",&bx[i]); int x=bx[i]; for(int j=1;j<=cnt;j++) while(x%c[j]==0) x/=c[j]; for(int j=2;j*j<=x;j++) if(x%j==0) { c[++cnt]=j; while(x%j==0) x/=j; } if(x!=1) c[++cnt]=x; } std::sort(c+1,c+cnt+1); dfs(1,1,1); std::sort(a+1,a+tot+1); sieve(); for(int i=1;i<=cnt;i++) for(int j=1;j<=tot;j++) if(a[j]%c[i]==0) s[a[j]]=(s[a[j]]+(ll)s[a[j]/c[i]]*c[i])%p; for(int i=1;i<=tot;i++) s[a[i]]=s[a[i]]*query(n/a[i])%p; for(int i=1;i<=cnt;i++) for(int j=tot;j>=1;j--) if(a[j]%c[i]==0) s[a[j]/c[i]]=(s[a[j]/c[i]]+(ll)s[a[j]]*c[i])%p; for(int i=1;i<=q;i++) printf("%lld\n",(s[bx[i]]+p)%p); return 0;}