BZOJ 2693 jzptab 莫比烏斯反演

2019-11-06 06:34:46

字體：大中小

來源：轉載

供稿：網友

BZOJ 2693 jzptab 莫比烏斯反演題目大意：給定n,m，求i從1到n，j從1到m，的i與j的最小公倍數之和。這題真的是有問題，難想的一批，公式恐懼癥無藥可救患者。。。。。。以下我們繼續給出PoPoQQQ的PPT中的內容，當中做出一些解釋。這里寫圖片描述注解：這里的F(x,y)要求gcd（i,j）==1，所以我們想要求解F(x,y)需要繼續莫比烏斯反演。注解：這里是一個標準的莫比烏斯反演，前面乘以一個i^2只是為了將除掉的i乘回來。

注解：我們注意到將公式全部打開之后出現了兩個整除，那么我們就通過換元來將di變成一個與第二維沒有關系的東西從而提出來變成正常的前綴和形式，從而求解。這里寫圖片描述注解：積性函數即為滿足f(i*j)==f(i)*f(j)(gcd(i,j)==1)的函數，而且后面的式子為標準的狄利克雷卷積形式，積性函數乘以積性函數等于積性函數，兩個積性函數的狄利克雷卷積也是積性函數，我們可以利用這種性質來線性篩出我們想要求出的那一坨，具體辦法是質數手算，一個數中不包含另一個質數時利用兩個函數值相乘，一個數中包含另一個數時找規律推出應該是什么（能不能推出來就看臉吧QAQ）

#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> #define M 10001000 #define MOD 100000009 using namespace std; typedef long long ll; int PRime[1001001],tot; bool not_prime[M]; ll h[M],sum[M]; void Linear_Shaker() { int i,j; h[1]=1; for(i=2;i<M;i++) { if(!not_prime[i]) { prime[++tot]=i; h[i]=(i-(ll)i*i)%MOD; } for(j=1;prime[j]*i<M;j++) { not_prime[prime[j]*i]=1; if(i%prime[j]==0) { h[prime[j]*i]=(prime[j]*h[i])%MOD; break; } h[prime[j]*i]=(h[prime[j]]*h[i])%MOD; } } for(i=1;i<M;i++) sum[i]=(sum[i-1]+h[i])%MOD; } inline ll Sum(ll x,ll y) { x%=MOD;y%=MOD; ll re1=(x*(x+1)>>1)%MOD; ll re2=(y*(y+1)>>1)%MOD; return re1*re2%MOD; } int Query(int n,int m) { int i,last,re=0; if(n>m) swap(n,m); for(i=1;i<=n;i=last+1) { last=min(n/(n/i),m/(m/i)); re+=Sum(n/i,m/i)*(sum[last]-sum[i-1])%MOD; re%=MOD; } return (re+MOD)%MOD; } int main() { int T,n,m; Linear_Shaker(); for(cin>>T;T;T--) { scanf("%d%d",&n,&m); printf("%d/n", Query(n,m) ); } }

上一篇：如何在C#中運行數學表達式字符串

下一篇：字符串復制strcpy()實現及常見問題