【BZOJ-4407】于神之怒加強版 莫比烏斯反演 + 線性篩

4407: 于神之怒加強版

Time Limit: 80 Sec  Memory Limit: 512 MB

Submit: 241  Solved: 119

[Submit][Status][Discuss]

Description

給下N,M,K.求

Input

輸入有多組資料，輸入資料的第一行兩個正整數T,K，代表有T組資料，K的意義如上所示，下面第二行到第T+1行，每行為兩個正整數N,M，其意義如上式所示。

Output

如題

Sample Input

1 2

3 3

Sample Output

20

HINT

1<=N,M,K<=5000000,1<=T<=2000

題解：JudgeOnline/upload/201603/4407.rar

Source

命題人：成都七中張耀楠，鳴謝excited上傳。

Solution

首先變換一下式子：

$$\sum_{d=1}^{n}d^{k}\sum_{i=1}^{n}\sum_{j=1}^{m}\left \lfloor gcd\left ( i,j \right )= d \right \rfloor$$

那麼我們設$f\left ( d \right )$表示$gcd\left ( i,j \right )= d$的點對的數目，那麼可以莫比烏斯反演得到：

$$f\left ( d \right )= \sum_{x=1}^{\left \lfloor \frac{n}{d} \right \rfloor}\mu \left ( x \right )\left \lfloor \frac{n}{dx} \right \rfloor\left \lfloor \frac{m}{dx} \right \rfloor$$

那麼就有：

 $$Ans= \sum_{d=1}^{n}d^{k}\times f(d)$$

但這還不夠求解，那麼令$y= dx$代換一下可以得到：

$$Ans= \sum_{y}^{n}\left \lfloor \frac{n}{y} \right \rfloor\left \lfloor \frac{m}{y} \right \rfloor\sum_{d|y}d^{k}\mu \left ( \frac{y}{d} \right )$$

到這一步就已經可以求解了：

令$g\left ( y \right )= \sum_{d|y}d^{k}\mu \left ( \frac{y}{d} \right )$，發現是積性函數，那麼線性篩處理出來即可

然後分塊求解即可。

Code

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
using namespace std;
int read()
{
    int x=0,f=1; char ch=getchar();
    while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}
    while (ch>='0' && ch<='9') {x=x*10+ch-'0'; ch=getchar();}
    return x*f;
}
#define maxn 5000010
#define p 1000000007
int T,K,N,M;
long long quick_pow(long long x,int y)
{
    long long re=1; x=x%p; y%=p;
    for (int i=y; i; i>>=1,x=x*x%p)
        if (i&1) re=re*x%p;
    return re;
}
bool flag[maxn];long long F[maxn],prime[maxn],cnt,sum[maxn];
void prework()
{
    flag[1]=1; F[1]=1; sum[1]=1;
    for (int i=2; i<maxn; i++)
        {
            if (!flag[i]) prime[++cnt]=i,F[i]=quick_pow(i,K)-1;
            for (int j=1; j<=cnt && i*prime[j]<maxn; j++)
                {
                    flag[i*prime[j]]=1;
                    if (!(i%prime[j]))
                        {F[i*prime[j]]=F[i]*quick_pow(prime[j],K)%p;break;}
                    else F[i*prime[j]]=F[i]*F[prime[j]]%p;
                }
            sum[i]=sum[i-1]+F[i]%p;
        }
}
void work(int n,int m)
{
    if (n>m) swap(n,m); 
    long long ans=0;
    for (int j,i=1; i<=n; i=j+1)
        j=min(m/(m/i),n/(n/i)),
        ans+=(sum[j]-sum[i-1]+p)%p*(n/i)%p*(m/i)%p,ans%=p;
    printf("%lld\n",ans);
}
int main()
{
    T=read(),K=read();
    prework();
    while (T--)
        {
            N=read(),M=read();
            work(N,M);
        }
    return 0;
}      

數論題做的巨心累，推了半天，毫無頭緒，最後默默看題解....zky學長說這是裸題...

轉載于:https://www.cnblogs.com/DaD3zZ-Beyonder/p/5341293.html