[SDOI2014]数表

题目大意：
　　$q(qleq2 imes10^4)$组询问，每次对于给定的$n,m,a(n,mleq10^5,aleq10^9)$，求$displaystylesum_{i=1}^nsum_{j=1}^m[sigma(gcd(i,j))leq a]sigma(gcd(i,j))$。

思路：
　　首先不考虑$a$的限制，原式=$displaystylesum_{d=1}^{min(n,m)}sigma(d)sum_{p=1}^{min(lfloorfrac n d floor,lfloorfrac m d floor)}mu(p)lfloorfrac n{dp} floorlfloorfrac m{dp} floor$。
　　令$T=dp$，则原式=$displaystylesum_{T=1}^{min(n,m)}lfloorfrac n T floorlfloorfrac m T floorsum_{d|T}sigma(d)mu(frac T d)$。
　　设$displaystyle g(T)=sum_{d|T}sigma(d)mu(frac T d)$，原式=$displaystylesum_{T=1}^{min(n,m)}lfloorfrac n T floorlfloorfrac m T floor g(T)$。
　　其中$g(T)$可以线性筛，求和可以数论分块。
　　考虑加入$a$的限制。按$a$的顺序离线处理询问，维护一个树状数组，其中第$i$位上的值$t_i$表示$g(i)$中$sigma(d)leq a$的数之和。可以先将所有的$sigma(d)$排序，然后每组询问把$leq a$的$sigma(d)$乘上对应的$mu$加入即可。

  1 #include<cstdio>
  2 #include<cctype>
  3 #include<climits>
  4 #include<algorithm>
  5 inline int getint() {
  6     register char ch;
  7     while(!isdigit(ch=getchar()));
  8     register int x=ch^'0';
  9     while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
 10     return x;
 11 }
 12 const int Q=2e4,N=1e5+1,P=9593;
 13 struct Query {
 14     int n,m,a,id;
 15     bool operator < (const Query &another) const {
 16         return a<another.a;
 17     }
 18 };
 19 Query q[Q];
 20 struct Func {
 21     int x,y;
 22     bool operator < (const Func &another) const {
 23         return y<another.y;
 24     }
 25 };
 26 Func sigma[N];
 27 bool vis[N];
 28 int ans[Q],p[P],mu[N];
 29 inline void sieve() {
 30     mu[1]=1;
 31     for(register int i=2;i<N;i++) {
 32         if(!vis[i]) {
 33             p[++p[0]]=i;
 34             mu[i]=-1;
 35         }
 36         for(register int j=1;j<=p[0]&&i*p[j]<N;j++) {
 37             vis[i*p[j]]=true;
 38             if(i%p[j]==0) {
 39                 mu[i*p[j]]=0;
 40                 break;
 41             }
 42             mu[i*p[j]]=-mu[i];
 43         }
 44     }
 45     for(register int i=1;i<N;i++) {
 46         sigma[i].x=i;
 47         for(register int j=i;j<N;j+=i) {
 48             sigma[j].y+=i;
 49         }
 50     }
 51     std::sort(&sigma[1],&sigma[N]);
 52 }
 53 class FenwickTree {
 54     private:
 55         int val[N];
 56         int lowbit(const int &x) const {
 57             return x&-x;
 58         }
 59     public:
 60         void modify(int p,const int &x) {
 61             while(p<N) {
 62                 val[p]+=x;
 63                 p+=lowbit(p);
 64             }
 65         }
 66         int query(int p) const {
 67             int ret=0;
 68             while(p) {
 69                 ret+=val[p];
 70                 p-=lowbit(p);
 71             }
 72             return ret;
 73         }
 74 };
 75 FenwickTree t;
 76 int main() {
 77     sieve();
 78     const int cnt_q=getint();
 79     for(register int i=0;i<cnt_q;i++) {
 80         const int n=getint(),m=getint(),a=getint();
 81         q[i]=(Query){n,m,a,i};
 82     }
 83     std::sort(&q[0],&q[cnt_q]);
 84     for(register int i=0,cur=1;i<cnt_q;i++) {
 85         for(;cur<N&&sigma[cur].y<=q[i].a;cur++) {
 86             for(register int j=sigma[cur].x;j<N;j+=sigma[cur].x) {
 87                 t.modify(j,sigma[cur].y*mu[j/sigma[cur].x]);
 88             }
 89         }
 90         const int &n=q[i].n,&m=q[i].m,&id=q[i].id,lim=std::min(n,m);
 91         for(register int i=1,j;i<=lim;i=j+1) {
 92             j=std::min(n/(n/i),m/(m/i));
 93             ans[id]+=(t.query(j)-t.query(i-1))*(n/i)*(m/i);
 94         }
 95     }
 96     for(register int i=0;i<cnt_q;i++) {
 97         printf("%d
",ans[i]&INT_MAX);
 98     }
 99     return 0;
100 }