微信如何建商城网站,新闻采集源码wordpress,注册德国网站域名,阿里云做哪里查网站正题
题目链接:https://www.luogu.com.cn/problem/P3172 题目大意
求有多少个长度为NNN的值域在[L,R][L,R][L,R]这个区间的序列满足它们的gcdgcdgcd恰好是KKK。 解题思路 dpdpdp容斥思想
我们先让L⌊LK−1K⌋,R⌊RK⌋L\lfloor\frac{LK-1}{K}\rfloor,R\lfloor\frac{R}{K}\rfl…正题
题目链接:https://www.luogu.com.cn/problem/P3172 题目大意
求有多少个长度为NNN的值域在[L,R][L,R][L,R]这个区间的序列满足它们的gcdgcdgcd恰好是KKK。 解题思路
dpdpdp容斥思想
我们先让L⌊LK−1K⌋,R⌊RK⌋L\lfloor\frac{LK-1}{K}\rfloor,R\lfloor\frac{R}{K}\rfloorL⌊KLK−1⌋,R⌊KR⌋这样就变成了让gcdgcdgcd是111。
然后设fif_{i}fi表示gcdgcdgcd恰好是iii时的方案。开始时若对于一个iii有xxx个数在[L,R][L,R][L,R]的区间内那么fixn−xf_ix^n-xfixn−x表示这个区间的公约数包含xxx且不完全相同时的方案数那么我们让所有的fif_ifi减去fk∗i(k∗i≤R−L)f_{k*i}(k*i\leq R-L)fk∗i(k∗i≤R−L)的最终值即可。
注意当L1L1L1时需要特判因为可以全是111。
杜教筛莫比乌斯反演思想
这里只是提及一下我也没写 定义f(x)f(x)f(x)表示gcdgcdgcd为xxx时的方案数ct(l,r,k)ct(l,r,k)ct(l,r,k)表示[l,r][l,r][l,r]区间kkk的倍数的个数 那么F(x)∑x∣df(d)ct(L,R,x)nF(x)\sum_{x|d}f(d)ct(L,R,x)^nF(x)x∣d∑f(d)ct(L,R,x)n f(k)∑k∣dF(dk)μ(d)∑i1⌊Rk⌋F(ik)μ(i)f(k)\sum_{k|d}F(\frac{d}{k})\mu(d)\sum_{i1}^{\lfloor\frac{R}{k}\rfloor}F(ik)\mu(i)f(k)k∣d∑F(kd)μ(d)i1∑⌊kR⌋F(ik)μ(i) 展开ctctct ⇒f(k)∑i1⌊Rk⌋(⌊Rik⌋−⌊L−1ik⌋)μ(i)\Rightarrow f(k)\sum_{i1}^{\lfloor\frac{R}{k}\rfloor}(\lfloor\frac{R}{ik}\rfloor-\lfloor\frac{L-1}{ik}\rfloor)\mu(i)⇒f(k)i1∑⌊kR⌋(⌊ikR⌋−⌊ikL−1⌋)μ(i)
然后整除分块前面那一部分后面那一部分杜教筛处理即可。 codecodecode
#includecstdio
#includecstring
#includealgorithm
#define ll long long
using namespace std;
const ll P1e97;
ll n,k,w,h,f[110000];
ll power(ll x,ll b){ll ans1;while(b){if(b1)ansans*x%P;xx*x%P;b1;}return ans;
}
int main()
{scanf(%lld%lld%lld%lld,n,k,w,h);w(wk-1)/k;hh/k;if(hw)return printf(0)0;for(ll i1;ih-w;i){ll xh/i-(wi-1)/i1;if(x0)continue;f[i](power(x,n)-xP)%P;}for(ll ih-w;i1;i--)for(ll j2*i;jh-w;ji)f[i](f[i]-f[j]P)%P;if(w1)f[1](f[1]1)%P;printf(%lld\n,f[1]);return 0;
}
