신의 분노 강화 판

링크
　　http://www.lydsy.com/JudgeOnline/problem.php?id=4407
해제
밤 에 불 을 켜 고 문 제 를 풀 고 모 비 우 스 를 꿈 꾼 다.
그래서 모 비 우 스 의 재연 이 었 다.n < m 를 제목 의 뜻 에 따라 우 리 는 식 을 쓴다.
ans=∑x=1nxk∑i=1⌊n/x⌋∑j=1⌊m/x⌋[gcd(i,j)=1]
경험 에 의 하면 우 리 는 안다
　　
ans=∑x=1nxk∑i=1⌊n/x⌋μ(i)⌊nix⌋⌊mix⌋
그리고 제 가 SB 폭력 을 썼어 요.
O (Tn 34) 가 T 를 건 네 주 었 다.
문제 풀이 에 근거 하여 우 리 는 배 웠 다.
　　
ans=∑x=1nxk∑x|dnμ(dx)⌊nd⌋⌊md⌋　　=∑d=1n⌊nd⌋⌊md⌋∑x|dxkμ(dx)
령.
g (x) = xk, 분명
g (x) 는 완전 적 함수 입 니 다.
그래서 오른쪽 에 있 는 덩어리 는 디 릭 레 의 볼 륨 이다.
령.
f(d)=(g∗μ)(d)
딜 릭 레 볼 륨 의 연산 성질 에 따라,
f (d) 도 적성 함수 다.
그래서.
f (d) 는 선형 체 로 접두사 와 그 다음 에 물 어 볼 때마다
O (N − √) 의 것 이다.
그렇다면 문제 가 생 겼 습 니 다. 어떻게 선형 체 입 니까? 구 조 는 국가 합숙 대 논문 을 참고 하 십시오. 임 지 주의 《 적 함수 구 화 를 위 한 몇 가지 방법 》 을 참고 하 십시오. 여 기 는 실현 하기 어 려 운 세부 사항 만 소개 합 니 다.
하나의 질 수 를 직접 계산 해 낼 수 있다.
f (x) = xk − 1, 이것 은 근거 이다.
dirchlet 볼 륨 의 정의 입 니 다. 서로 다른 질 로 나 눌 수 있 는 수 에 대해 서 는 직접 하면 됩 니 다.
하나의 소수 인자 만 있 는 수 에 대해 서 는 4 에서 8 을 내 놓 는 것 을 예 로 들 수 있다.
　　
f(4)=g(1)μ(4)+g(2)μ(2)+g(4)μ(1)
　　
f(8)=g(1)μ(8)+g(2)μ(4)+g(4)μ(2)+g(8)μ(1)
... 때문에
g 는 완전 적 함수 이기 때문에 상호 질 적 인 상황 을 고려 하지 않 고 직접 준다.
곱 하기
g (2), 획득
　　
f(4)g(2)=g(2)μ(4)+g(4)μ(2)+g(8)μ(1)
성공 에 가 까 워 진 것 같 습 니 다. 아직 부족 합 니 다.
g (1) f (8) 이거 어 떡 하지?
f (8) = 0 이기 때문에 이것 은 0 과 같 습 니 다. 따라서 곱 하기
g (2) 후에 우 리 는 얻 을 수 있다.
f (8) 됐어 요.
복잡 도: 분명히 소수 의 빠 른 멱 만 사용 해 야 하고 소수 의 개 수 는?
O (nlogn) 의 경우 알고리즘 의 복잡 도 는?
O(N) 。
총 복잡 도
O(N+TN−−√)
코드

//      
#include 
#include 
#define maxn 5000010
#define mod 1000000007
#define ll long long
using namespace std;
int x[maxn], K, prime[maxn], mark[maxn], tmp[maxn], f[maxn];
inline int fastpow(int a, int b, int p)
{
    int ans=1, t=a;
    for(;b;b>>=1,t=(ll)t*t%p)if(b&1)ans=(ll)ans*t%p;
    return ans;
}
void init()
{
    int i, j, t;
    f[1]=1;
    for(i=2;iif(!mark[i])
        {
            prime[++prime[0]]=i;
            tmp[i]=i;
            x[i]=fastpow(i,K,mod);
            f[i]=(x[i]-1+mod)%mod;
        }
        for(j=1;j<=prime[0] and i*prime[j]*prime[j];
            mark[t]=1;
            if(i%prime[j]==0)
            {
                tmp[t]=tmp[i]*prime[j];
                if(tmp[t]!=t)f[t]=(ll)f[t/tmp[t]]*f[tmp[t]]%mod;
                else f[t]=(ll)f[i]*x[prime[j]]%mod;
                break;
            }
            f[t]=(ll)f[i]*f[prime[j]]%mod;
            tmp[i*prime[j]]=prime[j];
        }
    }
    for(i=2;i1])%mod;
}
inline void calc(int n, int m)
{
    ll ans=0, lim=1e17;
    int i, last;
    if(n>m)swap(n,m);
    for(i=1;i<=n;i=last+1)
    {
        last=min(n/(n/i),m/(m/i));
        ans+=(ll)(n/i)*(m/i)%mod*(f[last]-f[i-1])%mod;
        if(ans>lim)ans%=mod;
    }
    printf("%d
",(int)(ans%mod+mod)%mod);
}
int main()
{
    int T, N, M;
    scanf("%d%d",&T,&K);
    for(init();T;T--)
    {
        scanf("%d%d",&N,&M);
        calc(N,M);
    }
    return 0;
}