题面:

4407: 于神之怒加强版

Time Limit: 80 Sec  Memory Limit: 512 MB

Submit: 702  Solved: 329

[][][]

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

题解：

　　$\sum_{i=1}^{n}\sum_{j=1}^{m}gcd(i,j)^{k}$

$=\sum_{d=1}^{min(n,m)}d^{k}\sum_{T=1}^{min(n,m)}\mu(\frac{T}{d})\lfloor\frac{n}{T}\rfloor\lfloor\frac{n}{T}\rfloor$

$=\sum_{T=1}^{min(n,m)}\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum_{d|T}{\mu(\frac{T}{d})d^{k}}$

令$f[T]=\sum_{d|T}{\mu(\frac{T}{d})d^k}$，之后线性筛求出$f[T]$前缀和，每个询问分块处理。

时间复杂度$O(N+T\sqrt{n})$。

1 #pragma GCC optimize("O3") 2 #include
       
         3 #include
        
          4 using namespace std; 5 const int mod=1e9+7; 6 const int maxn=5000000; 7 int prime[670000],g[maxn+1],f[maxn+1]; 8 bool book[maxn+1]; 9 int n,m,k,T,cnt;10 int qpow(int x,int y)11 {12     int ans=1;13     while(y)14     {15         if(y&1)16             ans=1LL*ans*x%mod;17         x=1LL*x*x%mod;18         y>>=1;19     }20     return ans;21 }22 void init()23 {24     g[1]=1;25     for(int i=2;i<=maxn;i++)26     { 27         if(!book[i])28         {29             prime[++cnt]=i;30             f[i]=qpow(i,k);31             g[i]=f[i]-1;        32         }33         for(int j=1;j<=cnt&&1LL*i*prime[j]<=maxn;j++)34         {35             book[i*prime[j]]=true;36             if(i%prime[j]!=0)37                 g[i*prime[j]]=1LL*g[i]*g[prime[j]]%mod;38             else39                 g[i*prime[j]]=1LL*g[i]*f[prime[j]]%mod;40         }41     }42     for(int i=2;i<=maxn;i++)43         g[i]=(g[i-1]+g[i])%mod;44      45 }46 int query(int x,int y)47 {48     int i,last;49     int ans=0;50     if(n>m)51         n^=m^=n^=m;52     for(i=1;i<=n;i=last+1)53     {54         last=min(n/(n/i),m/(m/i));55         ans=(ans+1LL*(n/i)*(m/i)%mod*(g[last]-g[i-1]+mod)%mod)%mod;56     }57     return ans;58 }59 int main()60 {61     scanf("%d%d",&T,&k);62     init();63     while(T--)64     {65         scanf("%d%d",&n,&m);66         printf("%d\n",query(n,m));67     }68 }
        
       

(PS:可以手动开$O_{2}O_{3}$(卡常数利器),可以快上几百ms)