C++14(g++5.4) 解法, 执行用时: 598ms, 内存消耗: 3432K, 提交时间: 2019-04-13 19:32:29

#include<bits/stdc++.h>
using namespace std;
#define MAXN 100005
#define n 100000
#define LL long long
#define pi pair<LL, int>

struct query{ int N, M, a, id; }q[20005];
bool cmp( query x, query y ){ return x.a < y.a; }
int Q, mu[MAXN], p[MAXN], tot;
pi f[MAXN];
int ans[20005], c[MAXN];
bool vis[MAXN];
inline void Add( int x, int y ){ for ( ; x <= n; x += x & -x ) c[x] += y; }
inline int Get( int x ){ int ans(0); for ( ; x; x -= x & -x ) ans += c[x]; return ans; }

int main(){
    scanf( "%d", &Q ); mu[1] = 1;
    for ( int i = 2; i <= n; ++i ){
        if ( !vis[i] ) p[++tot] = i, mu[i] = -1;
        for ( int j = 1; j <= tot && i * p[j] <= n; ++j ){
            vis[i * p[j]] = 1; if ( i % p[j] ) mu[i * p[j]] = -mu[i]; else break;
        }
    }
    for ( int i = 1; i <= n; ++i ){
        f[i].second = i;
        for ( int j = i; j <= n; j += i ) f[j].first += i;
    }
    sort( f + 1, f + n + 1 );
    for ( int i = 1; i <= Q; ++i ) scanf( "%d%d%d", &q[i].N, &q[i].M, &q[i].a ), q[i].id = i;
    sort( q + 1, q + Q + 1, cmp );
    
    for ( int T = 1, cur = 1; T <= Q; ++T ){
        while( f[cur].first <= q[T].a ){
            int x(f[cur].second);
            for ( int i = x; i <= n; i += x ) Add( i, f[cur].first * mu[i / x] );
            ++cur;
        }
        if ( q[T].N > q[T].M ) swap( q[T].N, q[T].M );
        for ( int i = 1, j; i <= q[T].N; i = j + 1 ){
            j = min( q[T].N / ( q[T].N / i ), q[T].M / ( q[T].M / i ) );
            ans[q[T].id] += ( q[T].N / i ) * ( q[T].M / i ) * ( Get(j) - Get(i - 1) );
        }
        if ( ans[q[T].id] < 0 ) ans[q[T].id] = ans[q[T].id] + ( 1 << 30 ) + ( 1 << 30 );
    }
    for ( int i = 1; i <= Q; ++i ) printf( "%d\n", ans[i] );
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 431ms, 内存消耗: 2936K, 提交时间: 2020-08-25 20:57:53

#include<cstdio>
#include<algorithm>
#define N 100000
using namespace std;
unsigned int s[N+2],g[N+2],v[N+2],p[N+2],id[N+2],u[N+2];
struct node{
	int n,m,a,id;unsigned int ans;
	bool operator<(const node&d)const{return a<d.a;}
}q[20002];
void inc(int i,unsigned int x){for(;i<=N;i+=-i&i)g[i]+=x;}
unsigned int query(int i){
	unsigned int ans=0;
	for(;i;i-=-i&i)ans+=g[i];
	return ans;
}
bool cmp2(node a,node b){return a.id<b.id;}
bool cmp(int a,int b){return s[a]<s[b];}
int main(){
	int T,i,j,k,r;
	//freopen("input.in","r",stdin);
	for(i=v[s[1]=u[1]=1]=2;i<=N;i++){
		if(!v[i]){
			u[v[i]=p[++p[0]]=i]=-1;
			s[i]=1+i;
		}
		for(j=1;j<=p[0]&&p[j]<=N/i;j++){
			if(i%p[j]){
				u[i*p[j]]=-u[i];
				s[i*p[j]]=(1+p[j])*s[i];
				v[i*p[j]]=p[j];
			}else{
				u[i*p[j]]=0;
				v[i*p[j]]=v[i]*p[j];
				s[i*p[j]]=s[i]+s[i/v[i]]*v[i]*p[j];
				break;
			}
		}
	}
	for(i=1;i<=N;i++)id[i]=i;
	sort(id+1,id+i,cmp);
	scanf("%d",&T);
	for(i=1;i<=T;i++)scanf("%d%d%d",&q[q[i].id=i].n,&q[i].m,&q[i].a);
	sort(q+1,q+i);
	for(k=r=1;k<=T;k++){
		for(;r<=N&&s[id[r]]<=q[k].a;r++)
			for(i=id[r];i<=N;i+=id[r])
				inc(i,s[id[r]]*u[i/id[r]]);
		if(q[k].n>q[k].m)swap(q[k].n,q[k].m);
		for(i=1;i<=q[k].n;i=j+1){
			j=min(q[k].n/(q[k].n/i),q[k].m/(q[k].m/i));
			q[k].ans+=1u*(query(j)-query(i-1))*(q[k].n/i)*(q[k].m/i);
		}
		q[k].ans&=0x7FFFFFFF;
	}
	sort(q+1,q+k,cmp2);
	for(i=1;i<=T;i++)printf("%u\n",q[i].ans);
	return 0;
}