DMY Round 51 D
[R51D]听取蛙声一片3
link.
计数DP.
设\(f_i\)表示以\(i\)为最小公倍数的方案数。
可以发现对\(f_i\)有贡献的只有\(i\)的因数，记为\(d_i\)。
容斥一下，可得\(f\)的递推式：
设\(i\)有\(m\)个因数（不包含\(i\)），\(k\)为\([1,i]\)中\(a_i\)的因数的个数。
\(f_i=2^k-1-\sum_{i=1}^{m}f_{d_i}\).
令\(m\)为\(n\)的因子个数。
时间复杂度：\(O(\sqrt n + mlogm + m^2)\).
code
#include <bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define inf 1e10
#define eps 1e-9
#define endl "\n"
#define il inline
#define ls 2*k
#define rs 2*k+1
using namespace std;
const int N=2e5+5,M=4e4;
const int mod=998244353;
inline int read(){int x=0,f=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();return x*f;
}
int n,a[N],top,f[N];
inline int ksm(int x,int y){int res=1;while(y){if(y&1) res=res*x%mod;x=x*x%mod;y>>=1;}return res%mod;
}
signed main(){ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);cin>>n;for(int i=1;i*i<=n;i++){if(n%i!=0) continue;int x=i,y=n/i;if(x==y) a[++top]=x;else{a[++top]=x;a[++top]=y;}}sort(a+1,a+top+1);for(int i=1;i<=top;i++){int d=0;for(int j=1;j<=i;j++)d+=(a[i]%a[j]==0);f[i]=(ksm(2ll,d)-1+mod)%mod;for(int j=1;j<i;j++)if(a[i]%a[j]==0)f[i]=((f[i]-f[j])%mod+mod)%mod;}cout<<f[top]%mod;return 0;
}