本文共 2161 字，大约阅读时间需要 7 分钟。

Description

有一张N×m的数表，其第i行第j列（1 < =i < =礼，1 < =j < =m）的数值为 能同时整除i和j的所有自然数之和。给定a，计算数表中不大于a的数之和。 Input 输入包含多组数据。 输入的第一行一个整数Q表示测试点内的数据组数，接下来Q行，每行三个整数n，m，a(|a| < =10^9)描述一组数据。 Output 对每组数据，输出一行一个整数，表示答案模2^31的值。 Sample Input 2 4 4 3 10 10 5 Sample Output 20 148 HINT 1 < =N．m < =10^5 ， 1 < =Q < =2×10^4 题解： 首先设$f(d)=\sum_{x|d}^{}x$ 那显然

$$Ans=\sum_{i=1}^{n}\sum_{j=1}^{m}f(gcd(i,j))$$ $$=\sum_{d=1}^{n}f(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\lfloor\frac{n}{id}\rfloor\lfloor\frac{m}{id}\rfloor\mu(i)$$ 设T=i*d; 则 $$Ans=\sum_{T=1}^{n}\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum_{d|T}{}f(d)\mu(\frac{T}{d})$$ 考虑没有a的限制我们直接搞一个后面项的前缀和即可。 现在有a我们显然不能这么搞。 考虑对于一个a,只有f(d)<=a的才有用。 所以我们所有询问按a排序,所有f数组从小到大排序。 依次处理询问,处理前把小于当前a的f(d)插入即可.每次询问两个前缀和即可。 这个东西显然可以用树状数组处理。 那么我们只用在线筛过程中处理出f数组即可。 每次取模考场上会T,需要改成自然溢出. 代码：

#include
   
    #include
    
     #include
     
      #include
      
       #define N 100010using namespace std;int T,t[N],ans[N],u[N],n,m,c[N],s[N];int p[N],f[N],tt,pos;struct use{
  int n,m,a,pos;}q[N];struct use2{
  int ss,pp;}g[N];bool cmp(use a,use b){
  return a.a
       
        >=1) if (b&1) ans*=a;  return ans;}void pre(){  u[1]=1;g[1].pp=g[1].ss=1;  for (int i=2;i<=n;i++){    if (!f[i]){p[++p[0]]=i;g[i].ss=s[i]=i+1;g[i].pp=i;c[i]=1;u[i]=-1;}    for (int j=1;j<=p[0]&&i*p[j]<=n;j++){      f[i*p[j]]=1;      if (i%p[j]==0){        c[i*p[j]]=c[i]+1;        s[i*p[j]]=s[i]+power(p[j],c[i]+1);        g[i*p[j]].ss=g[i].ss/s[i]*s[i*p[j]];        g[i*p[j]].pp=i*p[j];        break;      }     c[i*p[j]]=1;u[i*p[j]]=-u[i];g[i*p[j]].ss=g[i].ss*g[p[j]].ss;     s[i*p[j]]=p[j]+1;g[i*p[j]].pp=i*p[j];    }  }}void change(int k,int v){
  for (int i=k;i<=n;i+=(i&(-i)))t[i]+=v;}int ask(int k){  int ans(0);  for (int i=k;i;i-=(i&(-i))) ans+=t[i];  return ans;}int query(int n,int m){  int ans(0);  if (n>m) swap(n,m);  for (int i=1;i<=n;i=pos+1){    pos=min(n/(n/i),m/(m/i));    ans+=(ask(pos)-ask(i-1))*(n/i)*(m/i);  }   return ans&2147483647;}int main(){ scanf("%d",&T);n=N-10;tt=1;pre(); for (int i=1;i<=T;i++) scanf("%d%d%d",&q[i].n,&q[i].m,&q[i].a),q[i].pos=i; sort(q+1,q+T+1,cmp);sort(g+1,g+n+1,cmp2); for (int i=1;i<=T;i++){    while (g[tt].ss<=q[i].a&&tt<=n){      for (int j=g[tt].pp;j<=n;j+=g[tt].pp) change(j,g[tt].ss*u[j/g[tt].pp]);      tt++;    }  ans[q[i].pos]=query(q[i].n,q[i].m);  } for (int i=1;i<=T;i++) printf("%d\n",ans[i]);  }
       
      
     
    
   

转载地址：https://blog.csdn.net/sunshinezff/article/details/50961136 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！