北滘禅城网站建设,无症状感染者会自愈吗,免费建站的软件,王也天演员推荐在 cnblogs 上阅读。
【NOI2010】能量采集 题解
谨纪念我的第一道手推出来的莫反题。
题目大意#xff1a;已知 n n n#xff0c; m m m#xff0c;求 ∑ i 1 n ∑ j 1 m ( 2 ⋅ gcd ( i , j ) − 1 ) \sum\limits_{i1}^n\sum\limits_{j1}^m(2\cdot \gcd(i,j)…推荐在 cnblogs 上阅读。
【NOI2010】能量采集 题解
谨纪念我的第一道手推出来的莫反题。
题目大意已知 n n n m m m求 ∑ i 1 n ∑ j 1 m ( 2 ⋅ gcd ( i , j ) − 1 ) \sum\limits_{i1}^n\sum\limits_{j1}^m(2\cdot \gcd(i,j)-1) i1∑nj1∑m(2⋅gcd(i,j)−1)。
首先变形一手 ∑ i 1 n ∑ j 1 m ( 2 ⋅ gcd ( i , j ) − 1 ) 2 ∑ i 1 n ∑ j 1 m gcd ( i , j ) − n × m \sum\limits_{i1}^n\sum\limits_{j1}^m(2\cdot\gcd(i,j)-1)2\sum\limits_{i1}^n\sum\limits_{j1}^m\gcd(i,j)-n\times m i1∑nj1∑m(2⋅gcd(i,j)−1)2i1∑nj1∑mgcd(i,j)−n×m
然后我们只用求出中间那两个 ∑ \sum ∑ 就好了。 ∑ i 1 n ∑ j 1 m gcd ( i , j ) ∑ i 1 n ∑ j 1 m ∑ d 1 n d [ gcd ( i , j ) d ] ∑ d 1 n d ∑ i 1 ⌊ n d ⌋ ∑ j 1 ⌊ m d ⌋ [ gcd ( i , j ) 1 ] ∑ d 1 n d ∑ i 1 ⌊ n d ⌋ ∑ j 1 ⌊ m d ⌋ ∑ x ∣ gcd ( i , j ) μ ( x ) ∑ d 1 n d ∑ x 1 ⌊ n d ⌋ μ ( x ) ⌊ n d x ⌋ ⌊ m d x ⌋ \begin{aligned} \sum\limits_{i1}^n\sum\limits_{j1}^m\gcd(i,j)\sum\limits_{i1}^n\sum\limits_{j1}^m\sum\limits_{d1}^nd[\gcd(i,j)d]\\ \sum\limits_{d1}^nd\sum\limits_{i1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j1}^{\lfloor\frac{m}{d}\rfloor}[\gcd(i,j)1]\\ \sum\limits_{d1}^nd\sum\limits_{i1}^{\lfloor\frac{n}{d}\rfloor}\sum\limits_{j1}^{\lfloor\frac{m}{d}\rfloor}\sum\limits_{x|\gcd(i,j)}\mu(x)\\ \sum\limits_{d1}^nd\sum\limits_{x1}^{\lfloor\frac{n}{d}\rfloor} \mu(x)\lfloor\frac{n}{dx}\rfloor\lfloor\frac{m}{dx}\rfloor \end{aligned} i1∑nj1∑mgcd(i,j)i1∑nj1∑md1∑nd[gcd(i,j)d]d1∑ndi1∑⌊dn⌋j1∑⌊dm⌋[gcd(i,j)1]d1∑ndi1∑⌊dn⌋j1∑⌊dm⌋x∣gcd(i,j)∑μ(x)d1∑ndx1∑⌊dn⌋μ(x)⌊dxn⌋⌊dxm⌋
令 T d x Tdx Tdx ∑ d 1 n d ∑ x 1 ⌊ n d ⌋ μ ( x ) ⌊ n d x ⌋ ⌊ m d x ⌋ ∑ d 1 n d ∑ T 1 n μ ( T d ) ⌊ n T ⌋ ⌊ m T ⌋ [ d ∣ T ] ∑ T 1 n ⌊ n T ⌋ ⌊ m T ⌋ ∑ d 1 n d ⋅ μ ( T d ) [ d ∣ T ] ∑ T 1 n ⌊ n T ⌋ ⌊ m T ⌋ ∑ d ∣ T d ⋅ μ ( T d ) \begin{aligned} \sum\limits_{d1}^nd\sum\limits_{x1}^{\lfloor\frac{n}{d}\rfloor} \mu(x)\lfloor\frac{n}{dx}\rfloor\lfloor\frac{m}{dx}\rfloor \sum\limits_{d1}^nd\sum\limits_{T1}^n\mu(\frac{T}{d})\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor[d|T]\\ \sum\limits_{T1}^n\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum\limits_{d1}^nd\cdot\mu(\frac{T}{d})[d|T]\\ \sum\limits_{T1}^n\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum\limits_{d|T}d\cdot\mu(\frac{T}{d}) \end{aligned} d1∑ndx1∑⌊dn⌋μ(x)⌊dxn⌋⌊dxm⌋d1∑ndT1∑nμ(dT)⌊Tn⌋⌊Tm⌋[d∣T]T1∑n⌊Tn⌋⌊Tm⌋d1∑nd⋅μ(dT)[d∣T]T1∑n⌊Tn⌋⌊Tm⌋d∣T∑d⋅μ(dT)
如何处理后面那个 ∑ \sum ∑考虑狄利克雷卷积。不会的可以看我博客。
因为 φ ∗ I I d 1 \varphi*IId_1 φ∗IId1又因 I ∗ μ ϵ I*\mu\epsilon I∗μϵ所以 φ I d 1 ∗ μ \varphiId_1*\mu φId1∗μ
注意到右边那个 ∑ \sum ∑ 其实就是 I d 1 ∗ μ Id_1*\mu Id1∗μ即 φ \varphi φ。
所以可化为 ∑ T 1 n ⌊ n T ⌋ ⌊ m T ⌋ ∑ d ∣ T d ⋅ μ ( T d ) ∑ T 1 n ⌊ n T ⌋ ⌊ m T ⌋ ⋅ φ ( T ) \sum\limits_{T1}^n\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\sum\limits_{d|T}d\cdot\mu(\frac{T}{d})\sum\limits_{T1}^n\lfloor\frac{n}{T}\rfloor\lfloor\frac{m}{T}\rfloor\cdot\varphi(T) T1∑n⌊Tn⌋⌊Tm⌋d∣T∑d⋅μ(dT)T1∑n⌊Tn⌋⌊Tm⌋⋅φ(T)
很明显的整除分块预处理 φ \varphi φ 的前缀和就好了。
#includebits/stdc.h
using namespace std;#define int long longconst int N1e55;int n,m;
int cnt,pri[N],phi[N],mu[N],sum[N];
bool flg[N];void init()
{mu[1]1,phi[1]1;for(int i2;iN-5;i){if(!flg[i])pri[cnt]i,phi[i]i-1,mu[i]-1;for(int j1;jcntpri[j]*iN-5;j){flg[i*pri[j]]1;if(i%pri[j]0){phi[i*pri[j]]phi[i]*pri[j];break;}mu[i*pri[j]]-mu[i];phi[i*pri[j]]phi[i]*phi[pri[j]];}}for(int i1;iN-5;i)sum[i]sum[i-1]phi[i];
}int work(int n,int m)
{if(nm) swap(n,m);int res0;for(int l1,r;ln;lr1){rmin(n/(n/l),m/(m/l));res(sum[r]-sum[l-1])*(n/l)*(m/l);}return res;
}signed main()
{init();scanf(%lld%lld,n,m);printf(%lld\n,2*work(n,m)-n*m);return 0;
}
