【bzoj 3309 】 DZY Loves Math

2022-07-10 13:35:56

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)。

Input

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

Output

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

Sample Input

4
7558588 9653114
6514903 4451211
7425644 1189442
6335198 4957

Sample Output

35793453939901
14225956593420
4332838845846
15400094813

HINT

【数据规模】

T<=10000

1<=a,b<=10^7

题解：

　　Ｏ(≧口≦)Ｏ，不想写了……打一次数学公式半个多小时2333

　　贴一发题解：http://www.cnblogs.com/xkui/p/4598596.html

#include<cstdio>

using namespace std;

typedef long long ll;

inline ll min(ll a,ll b){return a<b?a:b;}

const ll mod=(ll)1e9+;

const int N=(int)1e7+;

ll n,m,k;

int prime[N];int num;

bool vis[N];

ll g[N];

int last[N],t[N];

void init(){

    for(int i=;i<N;i++){

        if(!vis[i]){

            prime[++num]=i;

            last[i]=t[i]=;

            g[i]=;

        }

        for(int j=;i*prime[j]<N&&j<=num;j++){

            int x=i*prime[j];

            vis[x]=;

            if(i%prime[j]==){

                last[x]=last[i];

                t[x]=t[i]+;

                if(last[x]==)

                    g[x]=;

                else

                    g[x]=(t[last[x]]==t[x]?-g[last[x]]:);

                break;

            }

            last[x]=i;

            t[x]=;

            g[x]=(t[i]==?-g[i]:);

        }

    }

    for(int i=;i<N;i++)

        g[i]+=g[i-];

}

inline ll solve(){

    ll ans=;

    if(m<n) n^=m^=n^=m;

    ll last;

    for(ll i=;i<=n;i=last+){

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

        ans+=(n/i)*(m/i)*(g[last]-g[i-]);

    }

    return ans;

}

int main(){

    int T;

    scanf("%ld",&T);

    init();

    while(T--){

        scanf("%lld%lld",&n,&m);

        ll ans=solve();

        printf("%lld\n",ans);

    }

}

码农公寓