出处：http://www.cnblogs.com/peng-ym/p/8660937.html （还是 建议 去看 原文）
题目：链接：https://www.luogu.org/problemnew/show/P3455
#include<bits/stdc++.h> #define LL long long #define ULL unsigned long long #define rep(i,j,k) for(int i=j;i<=k;i++) #define dep(i,j,k) for(int i=k;i>=j;i--) #define INF 0x3f3f3f3f #define mem(i,j) memset(i,j,sizeof(i)) #define make(i,j) make_pair(i,j) #define pb push_back using namespace std; const int N=5e5+5; bool vis[N]; int pre[N],sum[N],mu[N],tot; void init() {mu[1]=1;rep(i,2,500000) {if(!vis[i]) { pre[++tot]=i; mu[i]=-1 ; }rep(j,1,tot) {if(i*pre[j]>N-5) break;vis[i*pre[j]]=1;if(i%pre[j]==0) break;mu[i*pre[j]]=-mu[i];}}rep(i,1,N-5) sum[i]=sum[i-1]+mu[i]; } int main() {init();int t,n,m,k;scanf("%d",&t);while(t--) {scanf("%d %d %d",&n,&m,&k);int up=min(n/k,m/k);LL ans=0;for(int l=1,r;l<=up;l=r+1) {r=min((n/k)/((n/k)/l),(m/k)/((m/k)/l));ans+=1LL*((n/k)/l)*((m/k)/l)*(sum[r]-sum[l-1]);}printf("%lld\n",ans);}return 0; }
