BZOJ 4407: 신의 분노 강화판 | 모비우스 반연

수학 공식을 못해서 고민이에요!!flag: 수학 공식을 쓴 후에 꼭 문제 풀이를 잘 쓰도록 하겠습니다. 감사합니다.
Ans=∑i=1n∑j=1mgcd(i,j)k
설치하다
f(d)는
gcd(x, y)=d의
(x, y) 쌍수
g(d)=∑i=1⌊nd⌋f(i∗d)=⌊nd⌋∗⌊md⌋
f(d)=∑i=1⌊nd⌋u(i)∗g(i∗d)=∑i=1⌊nd⌋u(i)∗⌊md∗i⌋∗⌊nd∗i⌋
Ans=∑d=1ndk∑i=1⌊nd⌋u(i)∗⌊md∗i⌋∗⌊nd∗i⌋
이때 두 번 블록을 나누면 한 번의 심문을 할 수 있다
O(n)하지만 아직 부족해요.
계속 등가 변환령
T=d∗i
Ans=∑T=1n⌊nT⌋∗⌊mT⌋∑d|Tdk∗u(Td)
h(T)=∑d|Tdk∗u(Td)
만들기만 하면 돼요.
h(T)의 접두사와 블록으로 처리하면 단일 질문을 할 수 있습니다.
n√의 복잡도
그 다음은 귀신 짐승의 선형 체인데, 용님께 감사를 드려야 한다.

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#define N 5000005
#define ll long long
#define R 1000000007ll
using namespace std;
int sc()
{
    int i=0,f=1; char c=getchar();
    while(c>'9'||c<'0'){if(f=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9')i=i*10+c-'0',c=getchar();
    return i;
}
ll f[N],K;
int prime[N],low[N];
int a[N],n;
ll cal(ll x)
{
    ll ans=1,y=K;
    while(y)
    {
        if(y&1)ans=ans*x%R;
        x=x*x%R;
        y>>=1;
    }
    return (ans-1+R)%R;
}
void pre()
{
    int top=0; f[1]=low[1]=1;
    for(int i=2;iif(!a[i])
        {
            low[i]=prime[++top]=i;
            f[i]=cal(i);
        }
        for(int j=1;i*prime[j]*prime[j]]=1;
            if(i%prime[j]==0)
            {
                low[i*prime[j]]=low[i]*prime[j];
                if(low[i]==i) 
                    f[i*prime[j]]=f[i]*(f[prime[j]]+1)%R;
                else
                    f[i*prime[j]]=f[i/low[i]]*f[low[i]*prime[j]]%R;
                break;
            }
            low[i*prime[j]]=prime[j];
            f[i*prime[j]]=f[i]*f[prime[j]]%R;
        }
    }
    for(int i=2;i1])%R;
}
int main()
{
    n=sc(),K=sc();
    pre();
    while(n--)
    {
        ll ans=0;
        int n=sc(),m=sc();
        if(n>m)swap(n,m);
        for(int i=1,last;i<=n;i=last+1)
        {
            last=min(n/(n/i),m/(m/i));
            ans=(ans+((ll)(n/i)*(m/i)%R)*(R+f[last]-f[i-1])%R)%R;
        }
        printf("%lld
",ans);
    }
    return 0;
}