这题求[1,n],[1,m]gcd为k的对数。而且没有顺序。

设F(n)为公约数为n的组数个数 

f(n)为最大公约数为n的组数个数

然后在纸上手动验一下F(n)和f(n)的关系，直接套公式就好了。注意要删去重复的。

关于  的结论

ACdreamers大神的相关博客　　 　　

#include
     
      using namespace std;typedef long long LL;const int maxn=1e6;int prime[maxn+5];bool check[maxn+5];int mu[maxn+5];void init(){    mu[1]=1;    int tot=0;    for(int i=2;i<=maxn;i++)    {        if(!check[i])        {            prime[tot++]=i;            mu[i]=-1;        }        for(int j=0;j
      
       maxn) break;            check[i*prime[j]]=true;            if(i%prime[j]==0)            {                mu[i*prime[j]]=0;                break;            }            else            {                mu[i*prime[j]]=-mu[i];            }        }    }}int main(){    int T;    int a,b,c,d,k;    init();    scanf("%d",&T);    for(int kase=1;kase<=T;kase++)    {        scanf("%d%d%d%d%d",&a,&b,&c,&d,&k);        if(k==0)        {             printf("Case %d: 0\n",kase);             continue;        }        b/=k;        d/=k;        if(b>d) swap(b,d);        LL ans=0;        for(int i=1;i<=b;i++)            ans+=(LL)mu[i]*(b/i)*(d/i);        LL t=0;        for(int i=1;i<=b;i++)            t+=(LL)mu[i]*(b/i)*(b/i);        ans-=t/2;        printf("Case %d: %I64d\n",kase,ans);    }}