BZOJ2693：JZPTAP——题解

http://www.lydsy.com/JudgeOnline/problem.php?id=2693

Description

 

Input

一个正整数T表示数据组数

接下来T行 每行两个正整数 表示N、M

Output

T行 每行一个整数 表示第i组数据的结果

Sample Input

1
4 5

Sample Output

122

——————————————————————————————————————————

图片和题解参考均来自于https://www.cnblogs.com/GXZlegend/p/7000042.html以其这里面的链接。

推导过程如图：

这里说一下比较不好理解的步骤。

将每一行边号从1开始。

2：只是变成了枚举gcd的取值，然后判断是否应该取即可。

3：i变成了i/p之后自然需要乘p*p，一约分就成了3式子。

以及最后一个fn当中的所有k应当为n。

然后引用上面的博客来求fn：

#include<cstdio>

#include<queue>

#include<cctype>

#include<cstring>

#include<cmath>

#include<iostream>

#include<algorithm>

using namespace std;

typedef long long ll;

const int N=;

const int p=1e8+;

inline int read(){

    int X=;char ch=;

    while(!isdigit(ch))ch=getchar();

    while(isdigit(ch))X=(X<<)+(X<<)+(ch^),ch=getchar();

    return X;

}

ll f[N],su[N];

bool he[N];

inline ll s(ll x){

    return x*(x+)/%p;

}

void Euler(int n){

    int tot=;

    f[]=;

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

    if(!he[i]){

        su[++tot]=i;

        f[i]=(ll)((i-(ll)i*i)%p+p)%p;

    }

    for(int j=;j<=tot;j++){

        if(i*su[j]>n)break;

        he[i*su[j]]=;

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

        f[i*su[j]]=f[i]*su[j]%p;

        break;

        }

        else f[i*su[j]]=f[i]*f[su[j]]%p;

    }

    }

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

    f[i]+=f[i-];

    if(f[i]>=p)f[i]-=p;

    }

    return;

}

int main(){

    Euler();

    int t=read();

    while(t--){

    int n=read(),m=read(),ans=;

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

    for(int i=,j;i<=n;i=j+){

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

        ans+=(ll)(f[j]-f[i-])*s(n/i)%p*s(m/i)%p;

        if(ans<)ans+=p;

        if(ans>=p)ans-=p;

    }

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

    }

    return ;

}