1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72
| #include<cstdio> #include<cstring> #include<algorithm> using namespace std;
const int Q=2e4+10,N=1e5+10; const unsigned MOD=(unsigned)2147483648; #define ci const int & #define lowbit(x) ((x)&((-x)))
bool vis[N]; int cas,nprm,qry[Q][3],qid[Q],prm[N]; unsigned tre[N],mu[N],ans[Q]; pair<unsigned,int> sig[N];
inline int Read(){ register int r=0,c=getchar(); while(c<'0' || '9'<c) c=getchar(); while('0'<=c && c<='9') r=(r<<1)+(r<<3)+(c^'0'),c=getchar(); return r; } bool cmp(ci a,ci b){return qry[a][2]<qry[b][2];} void Update(int pos,ci key){while(pos<N) tre[pos]+=key,pos+=lowbit(pos);} unsigned Query(int pos){unsigned ret=0;while(pos) ret+=tre[pos],pos-=lowbit(pos);return ret;} void Init(){ for(int i=1;i<N;i++){ for(int j=1;j*j<=i;j++) if(i%j==0){ sig[i].first+=(unsigned)j; if(j*j!=i) sig[i].first+=(unsigned)i/j; } sig[i].second=i; } sort(sig+1,sig+N); mu[1]=1; for(int i=2;i<N;i++){ if(!vis[i]) mu[prm[++nprm]=i]--; for(int j=1;j<=nprm && prm[j]*i<N;j++){ vis[prm[j]*i]=true; if(i%prm[j]==0) break; mu[prm[j]*i]=-mu[i]; } } } int main(){ Init(); cas=Read(); for(int i=1;i<=cas;i++){ qry[i][0]=Read(),qry[i][1]=Read(),qry[i][2]=Read(); qid[i]=i; } sort(qid+1,qid+1+cas,cmp); for(int I=1,pos=1;I<=cas;I++){ int i=qid[I],A=qry[i][2]; while(pos<N && sig[pos].first<=(unsigned)A){ int num=sig[pos].second; for(int j=num;j<N;j+=num) Update(j,mu[j/num]*sig[pos].first); pos++; } unsigned n=(unsigned)qry[i][0],m=(unsigned)qry[i][1]; if(n>m) swap(n,m); for(unsigned j=1;j<=n;j++){ unsigned k=min(n/(n/j),m/(m/j)); ans[i]+=(n/j)*(m/j)*(Query(k)-Query(j-1)); j=k; } } for(int i=1;i<=cas;i++) printf("%d\n",ans[i]%MOD); return 0; }
|