BZOJ4833: [Lydsy1704月赛]最小公倍佩尔数
Problem
傳送門
Sol
容易得到
fn=en?1+fn?1,en?1=fn?1+en?1,f1=e1=1f_n=e_{n-1}+f_{n-1},e_{n-1}=f_{n-1}+e_{n-1},f_1=e_1=1fn?=en?1?+fn?1?,en?1?=fn?1?+en?1?,f1?=e1?=1
那么
fn=2×∑i=1n?1fi?fn?1+1f_n=2\times \sum_{i=1}^{n-1}f_i-f_{n-1}+1fn?=2×i=1∑n?1?fi??fn?1?+1
又有
fn+1=2×∑i=1nfi?fn+1f_{n+1}=2\times \sum_{i=1}^{n}f_i-f_{n}+1fn+1?=2×i=1∑n?fi??fn?+1
相減得到 fn+1=fn×2+fn?1,f1=1f_{n+1}=f_n\times 2 + f_{n-1},f_1=1fn+1?=fn?×2+fn?1?,f1?=1
有結(jié)論 gcd(a,b)=1gcd(a,b)=1gcd(a,b)=1 時，形如 fi=afi?1+bfi?2f_i=af_{i-1}+bf_{i-2}fi?=afi?1?+bfi?2? 的數(shù)列有性質(zhì) gcd(fi,fj)=fgcd(i,j)gcd(f_i,f_j)=f_{gcd(i,j)}gcd(fi?,fj?)=fgcd(i,j)?
大概可以這么證明
而 lcmlcmlcm 實際上是一個對于質(zhì)因子的指數(shù)取 maxmaxmax 的操作
每個質(zhì)因子分開考慮，然后最值反演
lcm(S)=∏ipi∑T?Smin(Ti)(?1)∣T∣+1=∏i∏T?Spimin(Ti)(?1)∣T∣+1lcm(S)=\prod_{i}p_i^{\sum_{T\subset S}min(T_i)(-1)^{|T|+1}}=\prod_{i}\prod_{T\subset S}p_i^{min(T_i)(-1)^{|T|+1}}lcm(S)=i∏?pi∑T?S?min(Ti?)(?1)∣T∣+1?=i∏?T?S∏?pimin(Ti?)(?1)∣T∣+1?
交換順序得到
lcm(S)=∏T?Sgcd(T)(?1)∣T∣+1lcm(S)=\prod_{T \subset S}gcd(T)^{(-1)^{|T|+1}}lcm(S)=T?S∏?gcd(T)(?1)∣T∣+1
其中 S,T≠?S,T\ne \emptyS,T??=?，min(Ti)min(T_i)min(Ti?) 表示 pip_ipi? 這個因子的指數(shù)最小值
所以
gn=∏T?Sfgcd(T)(?1)∣T∣+1=∏d=1nfd∑T?S[gcd(T)==d](?1)∣T∣+1g_n=\prod_{T \subset S}f_{gcd(T)}^{(-1)^{|T|+1}}=\prod_{d=1}^{n}f_ze8trgl8bvbq^{\sum_{T\subset S}[gcd(T)==d](-1)^{|T|+1}}gn?=T?S∏?fgcd(T)(?1)∣T∣+1?=d=1∏n?fd∑T?S?[gcd(T)==d](?1)∣T∣+1?
設(shè) sd=∑T?S[gcd(T)==d](?1)∣T∣+1s_d=\sum_{T\subset S}[gcd(T)==d](-1)^{|T|+1}sd?=T?S∑?[gcd(T)==d](?1)∣T∣+1
hi=∑i∣dnsd=∑T?S[i∣gcd(T)](?1)∣T∣+1=[cnti≠0]=1h_i=\sum_{i|d}^{n}s_d=\sum_{T\subset S}[i|gcd(T)](-1)^{|T|+1}=[cnt_i\ne 0]=1hi?=i∣d∑n?sd?=T?S∑?[i∣gcd(T)](?1)∣T∣+1=[cnti???=0]=1
其中 cnticnt_icnti? 表示 iii 的倍數(shù)的個數(shù)
那么
si=∑i∣dnμ(di)hd=∑i∣dnμ(di)s_i=\sum_{i|d}^{n}\mu(\fracze8trgl8bvbq{i})h_d=\sum_{i|d}^{n}\mu(\fracze8trgl8bvbq{i})si?=i∣d∑n?μ(id?)hd?=i∣d∑n?μ(id?)
那么
gn=∏d=1nfd∑d∣inμ(id)=∏d=1n∏d∣infdμ(id)=∏i=1n∏d∣ifdμ(id)g_n=\prod_{d=1}^{n}f_ze8trgl8bvbq^{\sum_{d|i}^{n}\mu(\frac{i}ze8trgl8bvbq)}=\prod_{d=1}^{n}\prod_{d|i}^{n}f_d^{\mu(\frac{i}ze8trgl8bvbq)}=\prod_{i=1}^{n}\prod_{d|i}f_d^{\mu(\frac{i}ze8trgl8bvbq)}gn?=d=1∏n?fd∑d∣in?μ(di?)?=d=1∏n?d∣i∏n?fdμ(di?)?=i=1∏n?d∣i∏?fdμ(di?)?
Θ(nlogn)\Theta(nlog n)Θ(nlogn) 預處理出 ∏d∣ifdμ(id)\prod_{d|i}f_d^{\mu(\frac{i}ze8trgl8bvbq)}∏d∣i?fdμ(di?)? 即可
總結(jié)
以上是生活随笔為你收集整理的BZOJ4833: [Lydsy1704月赛]最小公倍佩尔数的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 计算机cpu和显卡的搭配要求,如何搭配C
- 下一篇： 解决 Unable to determi