有一個M * N的表格,行與列分别是1 - M和1 - N,格子中間寫着行與列的最大公約數Gcd(i, j)(1 <= i <= M, 1 <= j <= N)。
例如:M = 5, n = 4。
1 2 3 4 5
1 1 1 1 1 1
2 1 2 1 2 1
3 1 1 3 1 1
4 1 2 1 4 1
給出M和N,求這張表中有多少個質數。
Input
第1行:一個數T,表示後面用作輸入測試的數的數量。(1 <= T <= 1000)
第2 - T + 1行:每行2個數M,N,中間用空格分隔,表示表格的寬和高。(1 <= M, N <= 5 * 10^6)
Output
共T行,每行1個數,表示表格中質數的數量。
Input示例
2
10 10
100 100
Output示例
30
2791
分析:
容易想到是枚舉質數p,然後推導公式。然而就是這麼做。
推導:
預設n<=m
[s]表示如果s為真,則表達是為1,[p]表示p為質數是為1,否則為0;
ANS(m,n)=∑p∑i=1⌊np⌋∑j=1⌊mp⌋[(i,j)=1][p]=∑p∑i=1⌊np⌋∑j=1⌊mp⌋∑k=1μ(k)[k|i,k|j][p]=∑p∑k=1⌊np⌋∑i=1⌊nkp⌋∑j=1⌊mkp⌋μ(k)[p]=∑k=1n∑p=1⌊nk⌋⌊nkp⌋⌊mkp⌋μ(k)[p]=∑k=1n∑p|k⌊nk⌋⌊mk⌋μ(kp)[p]=∑k=1n⌊nk⌋⌊mk⌋∑p|kμ(kp)[p]=∑k=1n⌊nk⌋⌊mk⌋f(k)
f(k) 可以打表,分析一下 f 的一些性質:
令 k=∏si=1pkii
如 ki 中一個大于2或者有兩個大于1,那麼f(k)=0;
了解起來也比較直覺。接着就可以遞推。
/*************************************************************************
> File Name: 1192.cpp
> Author: kelvin
> Mail: [email protected]
> Created Time: 2016年05月18日 星期三 10時49分45秒
************************************************************************/
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(int i=a;i<b;++i)
#define LL long long
#define mset(a,b) memset(a,b,sizeof a)
#define scan(n) scanf("%d",&n)
const int maxn = ;
const int mod = ;
int prime[maxn];
LL f[maxn];
int mu[maxn];
void getP()
{
mu[]=;
REP(i,,maxn){
if(!prime[i]){
prime[++prime[]]=i;
mu[i]=-;
f[i]=;
}
for(int j=;j<=prime[] && (LL)prime[j]*i<maxn;++j){
prime[i*prime[j]]=;
if(i%prime[j])
{
f[i*prime[j]]=mu[i]-f[i];
mu[i*prime[j]]=-mu[i];
}
else{
f[i*prime[j]]=mu[i];
break;
}
}
}
REP(i,,maxn) f[i]+=f[i-];
}
LL getans(int n,int m)
{
LL ret=;
for(int d=,j;d<=n;d=j+){
j=min(m/(m/d),n/(n/d));
ret+=(LL)(n/d)*(m/d)*(f[j]-f[d-]);
}
return ret;
}
int main()
{
getP();
int t;
scan(t);
int m,n;
while(t--){
scanf("%d%d",&m,&n);
if(n>m) swap(n,m);
LL ans=getans(n,m);
cout<<ans<<endl;
}
return ;
}