两学一做纪实评价系统登陆网站,著名室内设计师,沈阳网站建设公司排名,商丘seo公司甄选24火星正题
题目链接:http://www.51nod.com/Challenge/Problem.html#problemId1355 题目大意
定义fif_ifi表示斐波那契的第iii项#xff0c;给出一个大小为nnn的集合SSS求lcm(fS)lcm(f_S)lcm(fS) 解题思路
如果每个质数的次数分开考虑#xff0c;那么gcdgcdgcd就是次数取min…正题
题目链接:http://www.51nod.com/Challenge/Problem.html#problemId1355 题目大意
定义fif_ifi表示斐波那契的第iii项给出一个大小为nnn的集合SSS求lcm(fS)lcm(f_S)lcm(fS) 解题思路
如果每个质数的次数分开考虑那么gcdgcdgcd就是次数取minminminlcmlcmlcm就是次数取maxmaxmax所以可以套用min−maxmin-maxmin−max容斥的式子 lcm(S)∏T⊆Sgcd(T)(−1)∣T∣1lcm(S)\prod_{T\subseteq S}gcd(T)^{(-1)^{|T|1}}lcm(S)T⊆S∏gcd(T)(−1)∣T∣1 然后因为gcd(fx,fy)fgcd(x,y)gcd(f_x,f_y)f_{gcd(x,y)}gcd(fx,fy)fgcd(x,y)那么这题的答案 lcm(fS)∏T⊆Sfgcd(T)(−1)∣T∣1lcm(f_S)\prod_{T\subseteq S}f_{gcd(T)}^{(-1)^{|T|1}}lcm(fS)T⊆S∏fgcd(T)(−1)∣T∣1 这个好像算起来很麻烦我们可以分开考虑每个gcdgcdgcd的贡献。 定义fn∏d∣ngdf_n\prod_{d|n}g_dfn∏d∣ngd lcm(fS)∏T⊆S(∏d∣gcd(T)gd)(−1)∣T∣1lcm(f_S)\prod_{T\subseteq S}\left(\prod_{d|gcd(T)}g_d\right)^{(-1)^{|T|}1}lcm(fS)T⊆S∏⎝⎛d∣gcd(T)∏gd⎠⎞(−1)∣T∣1 lcm(fS)∏gd∑T⊆S[d∣gcd(T)](−1)∣T∣1lcm(f_S)\prod g_d^{\sum_{T\subseteq S}[d|gcd(T)](-1)^{|T|1}}lcm(fS)∏gd∑T⊆S[d∣gcd(T)](−1)∣T∣1 然后就是∑T⊆S[d∣gcd(T)](−1)∣T∣1\sum_{T\subseteq S}[d|gcd(T)](-1)^{|T|1}∑T⊆S[d∣gcd(T)](−1)∣T∣1因为没有了空集这个东西其实就相当于[∃ai∈S,d∣ai][\exists a_i\in S,d|a_i][∃ai∈S,d∣ai]。然后就可以直接枚举每个ddd来求答案了。 lcm(fS)∏∃ai∈S,d∣aigdlcm(f_S)\prod_{\exists a_i\in S,d|a_i} g_dlcm(fS)∃ai∈S,d∣ai∏gd
考虑ggg怎么构造我们有fn∏d∣ngdf_n\prod_{d|n}g_dfn∏d∣ngd直接移项就是gnfn−∏d∣n,d≠ngdg_nf_n-\prod_{d|n,d\neq n}g_dgnfn−∏d∣n,dngd就好了。
时间复杂度O(nlogn)O(n\log n)O(nlogn) code
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll N1e610,P1e97;
ll n,m,g[N],ans;
bool v[N];
ll power(ll x,ll b){ll ans1;while(b){if(b1)ansans*x%P;xx*x%P;b1;}return ans;
}
signed main()
{scanf(%lld,n);g[1]ans1;for(ll i1;in;i){ll x;scanf(%lld,x);mmax(m,x);v[x]1;}for(ll i2;im;i)g[i](g[i-1]g[i-2])%P;for(ll i1;im;i){ll invpower(g[i],P-2);for(ll j2*i;jm;ji)g[j]g[j]*inv%P;}for(ll i1;im;i){bool flag0;for(ll ji;jm;ji)if(v[j]){flag1;break;}if(flag)ans(ans*g[i])%P;}printf(%lld\n,ans);return 0;
}
