bzoj 3309
奇怪的莫比烏斯反演...
題意：定義$f(n)$表示將$n$質因數分解后質因子的最高冪次，求$\sum_{i=1}^{a}\sum_{j=1}^{b}f(gcd(i,j))$
首先肯定是反演嘛...
推一發式子：
$\sum_{i=1}^{a}\sum_{j=1}^{b}f(gcd(i,j))$
$\sum_{i=1}^{a}\sum_{j=1}^{b}\sum_{d=1}^{min(a,b)}[gcd(i,j)\equiv d]f(d)$
$\sum_{d=1}^{min(a,b)}f(d)\sum_{i=1}^{a}\sum_{j=1}^{b}[gcd(i,j)\equiv d]$
$\sum_{d=1}^{min(a,b)}f(d)\sum_{i=1}^{\frac{a}w0obha2h00}\sum_{j=1}^{\frac{b}w0obha2h00}[gcd(i,j)\equiv 1]$
$\sum_{d=1}^{min(a,b)}f(d)\sum_{i=1}^{\frac{a}w0obha2h00}\sum_{j=1}^{\frac{b}w0obha2h00}\sum_{t=1}^{min(\frac{a}w0obha2h00,\frac{b}w0obha2h00)}\mu(t)$
$\sum_{d=1}^{min(a,b)}f(d)\sum_{t=1}^{min(a,b)}\mu(t)\frac{a}{dt}\frac{b}{dt}$
令$T=dt$，得到：
$\sum_{T=1}^{min(a,b)}\frac{a}{T}\frac{b}{T}\sum_{d|T}f(d)\mu(\frac{T}w0obha2h00)$
于是我們只需線性篩后面那一坨，然后數論分塊即可
考慮線性篩：
令$g(T)=\sum_{d|T}f(d)\mu(\frac{T}w0obha2h00)$
設對$T$進行質因數分解，得到這樣的式子：$T=\prod_{i=1}^{n}p_{i}^{k_{i}}$
分兩類進行討論：
①.對任意$i\in [1,n-1]$，有$k_{i}=k_{i+1}$
首先我們考慮那個卷積式子，由于有一項是$\mu$，因此我們只需考慮$\mu$里面的東西無平方因子的情況，也即對于每個質因子，要么選$1$個，要么不選！
然后我們考慮什么分法會產生貢獻：
不難發現，我們取奇數個質因子和取偶數個質因子的方案數是一樣的，而其$\mu$互為相反數，當且僅當我們選了所有質因子時其$f$與其余的$f$不同（這個$f$變成了$k_{i}-1$），因此我們只需知道這個$-1$與對應的$\mu$產生的是正貢獻還是負貢獻即可，最后結論是$g(T)=(-1)^{n+1}$
②.存在$i,j\in [1,n]$，使得$k_{i}!=k_{j}$
類比上面的分析方式，得到$g(T)=0$
這樣就可以線性篩了
代碼：
#include <cstdio> #include <cmath> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> #include <queue> #include <stack> #define ll long long using namespace std; int mu[10000005]; int pri[1000005]; int f[10000005],mi[10000005],val[10000005]; ll F[10000005]; bool used[10000005]; int cnt=0; ll T,x,y; void init() { mu[1]=1; f[1]=0; for(int i=2;i<=10000000;i++) { if(!used[i])mu[i]=-1,pri[++cnt]=i,mi[i]=f[i]=1,val[i]=i; for(int j=1;j<=cnt&&i*pri[j]<=10000000;j++) { used[i*pri[j]]=1; if(i%pri[j]==0) { mu[i*pri[j]]=0; mi[i*pri[j]]=mi[i]+1; val[i*pri[j]]=val[i]*pri[j]; ll temp=i/val[i]; if(temp==1)f[i*pri[j]]=1; else f[i*pri[j]]=(mi[temp]==mi[i*pri[j]])?-f[temp]:0; break; } mu[i*pri[j]]=-mu[i],mi[i*pri[j]]=1,val[i*pri[j]]=pri[j],f[i*pri[j]]=(mi[i]==1)?-f[i]:0; } } for(int i=2;i<=10000000;i++)f[i]+=f[i-1]; } ll solve(ll a,ll b) { ll las=1,ans=0; for(int i=1;i<=a&&i<=b;i=las+1) { las=min(a/(a/i),b/(b/i)); ans+=(f[las]-f[i-1])*(a/i)*(b/i); } return ans; } template <typename T>inline void read(T &x) { T f=1,c=0;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){c=c*10+ch-'0';ch=getchar();} x=c*f; } int main() { init(); read(T); while(T--) { read(x),read(y); printf("%lld\n",solve(x,y)); } return 0; }
浙公網安備 33010602011771號