题意：
给出n,m求满足以下条件的方案数
-
a
i
∈
[
l
i
,
r
i
]
(
i
∈
[
1
,
n
]
)
a_i \in [l_i,r_i] (i\in[1,n])
ai?∈[li?,ri?](i∈[1,n])
-
∑
i
=
1
n
a
i
≤
m
\sum_{i=1}^na_i\leq m
∑i=1n?ai?≤m
-
gcd
?
(
a
1
,
a
2
,
.
.
.
,
a
n
)
=
1
\gcd(a_1,a_2,...,a_n)=1
gcd(a1?,a2?,...,an?)=1
结果对998244353取模
分析：
首先我们抛开第三个条件
g
c
d
gcd
gcd不看，那么这个就可以
O
(
n
m
)
O(nm)
O(nm)求，
n
≤
50
,
m
≤
1
e
5
n\leq50,m\leq 1e5
n≤50,m≤1e5所以不会超时。但是有了这个限制条件，我们就需要看看如果才能实现这个限制条件。
首先我们定义
f
(
a
1
,
a
2
,
.
.
.
a
n
)
=
∑
i
=
1
n
a
i
<
=
m
f(a_1,a_2,...a_n)=\sum_{i=1}^na_i<=m
f(a1?,a2?,...an?)=∑i=1n?ai?<=m
∑
a
i
=
l
1
r
1
∑
a
i
=
l
2
r
2
∑
a
i
=
l
3
r
3
.
.
.
.
∑
a
i
=
l
n
r
n
f
(
a
1
,
a
2
,
.
.
.
.
a
n
)
[
gcd
?
(
a
1
,
a
2
,
.
.
.
,
a
n
)
=
1
]
\sum_{a_i=l_1}^{r_1}\sum_{a_i=l_2}^{r_2}\sum_{a_i=l_3}^{r_3}....\sum_{a_i=l_n}^{r_n}f(a_1,a_2,....a_n)[\gcd(a_1,a_2,...,a_n)=1]
ai?=l1?∑r1??ai?=l2?∑r2??ai?=l3?∑r3??....ai?=ln?∑rn??f(a1?,a2?,....an?)[gcd(a1?,a2?,...,an?)=1]
这里我们看到
[
g
c
d
(
a
1
,
a
2
.
.
.
.
.
a
n
)
=
1
]
[gcd(a_1,a_2.....a_n)=1]
[gcd(a1?,a2?.....an?)=1]我们想到莫比乌斯反演。
∑
a
i
=
l
1
r
1
∑
a
i
=
l
2
r
2
∑
a
i
=
l
3
r
3
.
.
.
.
∑
a
i
=
l
n
r
n
f
(
a
1
,
a
2
,
.
.
.
.
a
n
)
∑
d
∣
gcd
?
(
a
1
,
a
2
,
.
.
.
,
a
n
)
μ
(
d
)
\sum_{a_i=l_1}^{r_1}\sum_{a_i=l_2}^{r_2}\sum_{a_i=l_3}^{r_3}....\sum_{a_i=l_n}^{r_n}f(a_1,a_2,....a_n)\sum_{d|\gcd(a_1,a_2,...,a_n)}\mu(d)
ai?=l1?∑r1??ai?=l2?∑r2??ai?=l3?∑r3??....ai?=ln?∑rn??f(a1?,a2?,....an?)d∣gcd(a1?,a2?,...,an?)∑?μ(d)
d
∣
gcd
?
(
a
1
,
a
2
,
.
.
.
,
a
n
)
d|\gcd(a_1,a_2,...,a_n)
d∣gcd(a1?,a2?,...,an?)说明
a
1
,
a
2
.
.
.
a
n
a_1,a_2...a_n
a1?,a2?...an?都是d的倍数。
∑
a
i
=
l
1
r
1
∑
a
i
=
l
2
r
2
∑
a
i
=
l
3
r
3
.
.
.
.
∑
a
i
=
l
n
r
n
f
(
a
1
,
a
2
,
.
.
.
.
a
n
)
∑
d
∣
a
1
&
d
∣
a
2
,
.
.
.
&
d
∣
a
n
μ
(
d
)
\sum_{a_i=l_1}^{r_1}\sum_{a_i=l_2}^{r_2}\sum_{a_i=l_3}^{r_3}....\sum_{a_i=l_n}^{r_n}f(a_1,a_2,....a_n)\sum_{d|a_1\&d|a_2,...\&d|a_n}\mu(d)
ai?=l1?∑r1??ai?=l2?∑r2??ai?=l3?∑r3??....ai?=ln?∑rn??f(a1?,a2?,....an?)d∣a1?&d∣a2?,...&d∣an?∑?μ(d)
提取d,发现d最大是m。
∑
d
=
1
m
μ
(
d
)
∑
a
i
=
l
1
d
r
1
d
∑
a
i
=
l
2
d
r
2
d
.
.
.
.
.
.
.
.
.
∑
a
i
=
l
n
d
r
n
d
f
(
a
1
,
a
2
,
.
.
.
.
a
n
)
\sum_{d=1}^{m}\mu(d)\sum_{a_i=\frac{l_1}{d}}^{\frac{r_1}{d}}\sum_{a_i=\frac{l_2}{d}}^{\frac{r_2}{d}}.........\sum_{a_i=\frac{l_n}{d}}^{\frac{r_n}{d}}f(a_1,a_2,....a_n)
d=1∑m?μ(d)ai?=dl1??∑dr1???ai?=dl2??∑dr2???.........ai?=dln??∑drn???f(a1?,a2?,....an?)
综上，我们会发现，如果
μ
(
d
)
\mu(d)
μ(d)等于0，后面的也就不用计算了。
f
(
)
f()
f()用DP来做就好了.
注意莫比乌斯反演最终形式不一定有整除分块的形式。
int prime[maxn],mu[maxn],l[maxn],r[maxn];
bool isprime[maxn];
int n,m, cnt;
ll a[maxn],b[maxn];
void init()
{
mu[1]=isprime[1]=1;
for(int i = 2; i < maxn; i++)
{
if(!isprime[i]) prime[++cnt] = i,mu[i]=-1;
for(int j = 1; j <= cnt && prime[j]*i < maxn; j++)
{
isprime[i * prime[j]] = true;
if(i % prime[j] == 0) break;
mu[i*prime[j]]=-mu[i];
}
}
}
int dp[maxn],f[maxn];
void solve()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)scanf("%d%d",&l[i],&r[i]);
ll ans=0;
for(int i=1;i<=m;i++){
if(mu[i]==0) continue;
for(int j=1;j<=n;j++){
a[j]=(l[j]+i-1)/i;
b[j]=r[j]/i;
}
int sum=m/i;
for(int j=0;j<=sum;j++) dp[j]=1;
for(int j=1;j<=n;j++){
for(int k=1;k<=sum;k++) f[k]=0;
for(int k=a[j];k<=sum;k++){
f[k]=dp[k-a[j]];
if(k-b[j]-1>=0) f[k]=(f[k]-dp[k-b[j]-1]+mod)%mod;
}
dp[0]=0;
for(int k=1;k<=sum;k++) dp[k]=(dp[k-1]+f[k])%mod;
}
ans+=dp[sum]*mu[i]%mod;
ans=(ans+mod)%mod;
}
cout<<ans<<endl;
}
|