Eva

Time Limit: 20 Sec  Memory Limit: 512 MB
Submit: 1843  Solved: 1195
Description

对于正整数n，定义f(n)为n所含质因子的最大幂指数。例如f(1960)=f(2^3 * 5^1 * 7^2)=3, f(10007)=1, f(1)=0。
给定正整数a,b，求sigma(sigma(f(gcd(i,j)))) (i=1..a, j=1..b)。

第一行一个数T，表示询问数。
接下来T行，每行两个数a,b，表示一个询问。

对于每一个询问，输出一行一个非负整数作为回答。

4
7558588 9653114
6514903 4451211
7425644 1189442
6335198 4957

35793453939901
14225956593420
4332838845846
15400094813

【数据规模】

T<=10000

1<=a,b<=10^7

/**************************************************************

    Problem: 3309

    User: ictsing

    Language: C++

    Result: Accepted

    Time:11320 ms

    Memory:206372 kb

****************************************************************/

 

//3309: DZY Loves Math

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

using namespace std;

const int mt = 10000000+5;

long long sum[mt];

int e[mt],g[mt],pri[mt];

bool vis[mt];

inline int read()

{

    int num=0,flag=1;

    char ch;

    do{

        ch=getchar();

        if(ch=='-') flag=-1;

    }while(ch<'0'||ch>'9');

    do{

        num=num*10+ch-'0';

        ch=getchar();

    }while(ch>='0'&&ch<='9');

    return num*flag;

}

void init()

{

    for(int i=2;i<=mt-5;i++)

    {

        if(!vis[i])

            pri[++pri[0]]=i,sum[i]=e[i]=1,g[i]=i;

        for(int j=1;1ll*i*pri[j]<=mt-5&&j<=pri[0];j++)

        {

            vis[i*pri[j]]=1;

            if(i%pri[j]==0)

            {

                g[i*pri[j]]=g[i]*pri[j];

                e[i*pri[j]]=e[i]+1;

                int tmp=i/g[i];

                if(tmp==1) sum[i*pri[j]]=1;

                else sum[i*pri[j]]=(e[tmp]==e[i*pri[j]])?-sum[tmp]:0;

                break;

            }

            else

            {

                g[i*pri[j]]=pri[j];

                e[i*pri[j]]=1;

                sum[i*pri[j]]=(e[i]==1)?-sum[i]:0;

            }

        }

    }

    for(int i=1;i<=mt-5;i++) sum[i]+=sum[i-1];

}

long long solve(int n,int m)

{

    if(n>m) swap(n,m);

    long long ans=0;

    for(int i=1,pos;i<=n;i=pos+1)

    {

        pos=min(n/(n/i),m/(m/i));

        ans+=1ll*(n/i)*(m/i)*(sum[pos]-sum[i-1]);

    }

    return ans;

}

int main()

{

    init();

    int T_T=read();

    for(int i=1;i<=T_T;i++)

    {

        int a=read(),b=read();

        printf("%lld\n",solve(a,b));

    }

    return 0;

}