Description

對于正整數(shù)n，定義f(n)為n所含質(zhì)因子的最大冪指數(shù)。例如f(1960)=f(2^3 * 5^1 * 7^2)=3, f(10007)=1, f(1)=0。
給定正整數(shù)a,b，求sigma(sigma(f(gcd(i,j)))) (i=1..a, j=1..b)。

Input

第一行一個數(shù)T，表示詢問數(shù)。
接下來T行，每行兩個數(shù)a,b，表示一個詢問。

Output

對于每一個詢問，輸出一行一個非負(fù)整數(shù)作為回答。

Sample Input

4
7558588 9653114
6514903 4451211
7425644 1189442
6335198 4957

Sample Output

35793453939901
14225956593420
4332838845846
15400094813

HINT

T<=10000
1<=a,b<=10^7

sol

先推式子，假設(shè)a<b，枚舉gcd：

\(ans=\sum_{i=1}^{a}\sum_{j=1}^{b}f(i,j)\)

\(=\sum_{d=1}^{a}f(d)\sum_{i=1}^{\lfloor\frac{a}ze8trgl8bvbq\rfloor}\sum_{j=1}^{\lfloor\frac{b}ze8trgl8bvbq\rfloor}[(i,j)=1]\)

\(=\sum_{d=1}^{a}f(d)\sum_{i=1}^{\lfloor\frac{a}ze8trgl8bvbq\rfloor}\mu(i)\lfloor\frac{a}{id}\rfloor\lfloor\frac{b}{id}\rfloor\)

\(=\sum_{T=1}^{a}\lfloor\frac{a}{T}\rfloor\lfloor\frac{b}{T}\rfloor\sum_{d|T}f(d)\mu(\frac{T}ze8trgl8bvbq)\)

前面那個玩意直接數(shù)論分塊就可以了，然后分析后面的式子：

我們只考慮沒有平方因子的T/d，那么此時f(d)的取值只有兩種：T最高次質(zhì)因數(shù)冪-1或者T最高次質(zhì)因數(shù)冪。

如果取的是最高次質(zhì)因數(shù)冪，那么我們發(fā)現(xiàn)，T/d中剩下的數(shù)字次數(shù)可以是0也可以是1，那么根據(jù)莫比烏斯函數(shù)的定義，\(\mu(\frac{T}ze8trgl8bvbq)\)一定等于0，不會產(chǎn)生任何貢獻。

如果取的是最高次質(zhì)因數(shù)冪-1，那么我們發(fā)現(xiàn)，滿足最高次冪的指數(shù)在T/d中都是1次項，其他數(shù)字隨意，根據(jù)莫比烏斯函數(shù)的定義，mu一定是0，不會產(chǎn)生任何貢獻。

所以現(xiàn)在只剩下了兩種情況：1.質(zhì)數(shù)2.d中所有次冪都相等

線性篩即可，線性篩處理出每個數(shù)字最高次質(zhì)因數(shù)冪和最高次質(zhì)因數(shù)冪的乘積，便可以在線性篩中直接判斷。

code

#include <bits/stdc++.h> using namespace std; int g[10000007],a[10000007],pri[10000007],vis[10000007],sum[10000007],ma[10000007],T,n,m,tot; long long cal(int a,int b) {if(a>b) swap(a,b);long long ans=0;for(int i=1,last=0;i<=a;i=last+1) last=min(a/(a/i),b/(b/i)),ans+=1ll*(a/i)*(b/i)*(sum[last]-sum[i-1]);return ans; } int main() {for(int i=2;i<=1e7;i++){if(!vis[i]){pri[++tot]=i;g[i]=1,a[i]=1;ma[i]=i;}for(int j=1,k;j<=tot&&(k=i*pri[j])<=1e7;j++){vis[k]=1;if(i%pri[j]==0){a[k]=a[i]+1;ma[k]=ma[i]*pri[j];if(i==ma[i]) g[k]=1;else g[k]=(a[i/ma[i]]==a[k]?-g[i/ma[i]]:0);}else a[k]=1,ma[k]=pri[j],g[k]=(a[i]==1?-g[i]:0);}sum[i]=sum[i-1]+g[i];}for(scanf("%d",&T);T--;printf("%lld\n",cal(n,m))) scanf("%d%d",&n,&m); }

轉(zhuǎn)載于:https://www.cnblogs.com/CK6100LGEV2/p/9393077.html

《新程序員》：云原生和全面數(shù)字化實踐50位技術(shù)專家共同創(chuàng)作，文字、視頻、音頻交互閱讀

總結(jié)

以上是生活随笔為你收集整理的【bzoj3309】DZY Loves Math 莫比乌斯反演+线性筛的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。