有一张n×m的数表，其第i行第j列（1 < =i < =n，1 < =j < =m）的数值为 能同时整除i和j的所有自然数之和。给定a，计算数表中不大于a的数之和。
输入包含多组数据。 输入的第一行一个整数Q表示测试点内的数据组数，接下来Q行，每行三个整数n，m，a(|a| < =10^9)描述一组数据。
对每组数据，输出一行一个整数，表示答案模2^31的值。
2
4 4 3
10 10 5
20
148
1 < =N．m < =10^5 ， 1 < =Q < =2×10^4
orz PoPoQQQ…… 基本想法同“YY的GCD” 线性筛可筛出每个数i的约数和s[i] 之后离线处理，将a与s[]分别从小到大排序处理，莫比乌斯反演，树状数组维护前缀和。
注意：诡异的取模需要注意一下。
#include<cstdio> #include<iostream> #include<algorithm> #define P 1<<31 using namespace std; typedef long long ll; const int N = 100005; int mu[N]; ll s[N],sm[N]; int p[N],prime[N],pnum; void getmu(){ mu[1]=s[1]=1; for(int i=2;i<N;i++) p[i]=1; for(int i=2;i<N;i++){ if(p[i]){ prime[pnum++]=i; mu[i]=-1; s[i]=sm[i]=1+i; } for(int j=0;j<pnum && (ll)prime[j]*i<N;j++){ int id=prime[j]*i; p[id]=0; if(i%prime[j]==0){ mu[id]=0; s[id]=s[i]/sm[i]*(sm[i]*prime[j]+1); sm[id]=sm[i]*prime[j]+1; break; } mu[id]=-mu[i]; s[id]=s[i]*(1+prime[j]); sm[id]=1+prime[j]; } } } int num[N]; bool cmp(int x,int y) { return s[x]<s[y]; } struct Bit{ ll c[N]; int lowbit(int x) { return x&(-x); } void add(int x,ll y){ while(x<N){ (c[x]+=y)%=P; x+=lowbit(x); } } ll sum(int x){ ll ret=0; while(x){ (ret+=c[x])%=P; x-=lowbit(x); } return ret; } }f; struct data{ int n,m,a,id; bool operator < (const data &b) const{ return a<b.a; } }d[N]; ll ans[N]; int main() { int T; getmu(); for(int i=1;i<N;i++) num[i]=i; sort(num+1,num+1+100000,cmp); scanf("%d",&T); for(int i=1;i<=T;i++){ scanf("%d%d%d",&d[i].n,&d[i].m,&d[i].a); d[i].id=i; } sort(d+1,d+1+T); int t=1,n,m; for(int i=1;i<=T;i++){ while(t<N && s[num[t]]<=d[i].a) { for(int j=1;(ll)j*num[t]<N;j++) f.add(j*num[t],s[num[t]]*mu[j]); t++; } n=d[i].n; m=d[i].m; for(int l=1,r;l<=min(n,m);l=r+1){ r=min(n/(n/l),m/(m/l)); ans[d[i].id]+=(f.sum(r)-f.sum(l-1))*(n/l)*(m/l); } } for(int i=1;i<=T;i++) printf("%lld\n",ans[i]&2147483647); return 0; }转载于:https://www.cnblogs.com/lindalee/p/8506720.html
