[HOJ] 22 - 駭客

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
long long int n,m,ans,A,B;
int s[50005]={0},add[50005],sum[50005]={0};
vector<int> num[50005];
int main(){
    int t,a,b,c,k,i,j;
    for(i=2;i<=50000;i++){
        if(s[i]==0){
            num[i].push_back(i);
            for(j=i+i;j<=50000;j+=i)
                s[j]=1,num[j].push_back(i);
        }
    }
    for(i=2;i<=50000;i++){
        add[i]=1;
        for(j=0;j<num[i].size();j++)
            add[i]*=num[i][j];
        sum[i]=sum[i-1];
        if(i==add[i]){
            if(num[i].size()%2)sum[i]--;
            else sum[i]++;
        }
    }
    scanf("%d",&t);
    while(t--){
        ans=0;
        scanf("%d%d%d",&a,&b,&c);
        if(a>b) swap(a,b);
        n=b/c;
        m=a/c;
        ans=n*m;
        for(i=2;i<=m;i++){
            A=n/i,B=m/i;
            A=n/A,B=m/B;
            A=min(A,B);
            A=min(A,m);
            ans+=(n/i)*(m/i)*(sum[A]-sum[i-1]),i=A;
        }
        printf("%lld\n",ans);
    }
}