记录编号	381853	评测结果	AAAAAAAAAA
题目名称	[SDOI 2015] 约数个数和	最终得分	100
用户昵称	sxysxy	是否通过	通过
代码语言	C++	运行时间	5.656 s
提交时间	2017-03-12 18:35:10	内存使用	1.12 MiB

#include <cstdio>
#include <cstring>
#include <cstdarg>
#include <list>
#include <queue>
#include <vector>
#include <algorithm>
#include <iostream>
using namespace std;
#define MAXP 50000
#define MAXN 50003
typedef long long LL;
int primes[MAXN], tot, miu[MAXN];
bool vis[MAXN];
LL d[MAXN];
void pre(){
  miu[1] = 1;
  for(int i = 2; i <= MAXP; i++){
    if(!vis[i]){
      primes[tot++] = i;
      miu[i] = -1;
    }
    for(int j = 0; j < tot; j++){
      int k = i*primes[j];
      if(k > MAXP)break;
      vis[k] = true;
      if(i%primes[j])miu[k] = -miu[i];
      else break;
    }
  }
  for(int i = 1; i <= MAXP; i++){
    for(int j = 1, k = 1; j <= i; j = k+1){
      k = i/(i/j);
      d[i] += (LL)(k-j+1)*(i/j);
    }
    miu[i] += miu[i-1];
  }
}
int main(){
  freopen("SDOI2015yue.in", "r", stdin);
  freopen("SDOI2015yue.out", "w", stdout);
  pre();
  int T; scanf("%d", &T);
  while(T--){
    int n, m; scanf("%d %d", &n, &m);
    if(n > m)swap(n, m);
    LL ans = 0;
    for(int i = 1, j = 1; i <= n; i = j+1){
      j = min(n/(n/i), m/(m/i));
      ans += (LL)(miu[j]-miu[i-1])*d[n/i]*d[m/i];
    }
    printf("%lld\n", ans);
  }
  return 0;
}