记录编号	406172	评测结果	AAAAAAATTT
题目名称	[HZOI 2016]艾米利亚的施法	最终得分	70
用户昵称	sxysxy	是否通过	未通过
代码语言	C++	运行时间	8.097 s
提交时间	2017-05-18 00:57:28	内存使用	200.56 MiB

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