P6280 [USACO20OPEN]Exercise G

[USACO20OPEN]Exercise G - 洛谷

算法标签：素数筛+计数类DP

难度：提高+/省选-

通过模拟可得到一下性质：

如果存在K=1，那么每一个a[ i ] = i；

如果存在K=2，那么每一个a[ a[ i ] ] = i；

如果存在K=3，那么每一个 a[ a[ a[ i ] ] ] = i；

其实也就是形成一个或多个长度为K的最小公倍数的环。

（注：之所以是最小公倍数，是因为有些环可以重复几次变成 i ，见样例！！！）

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define N 10010
#define ll long long
int n,m,cnt,p[N],isp[N];
ll dp[N],ans;

void Init ()
{
	cin>>n>>m;
	for (int i=2;i<=n;i++)
		if (!isp[i])
		{
			p[++cnt]=i;
			for (int j=i*i;j<=n;j+=i)
				isp[j]=1;
		}
}

void Work ()
{
	dp[0]=1;
	for (int i=1;i<=cnt;i++)
		for (int j=n;j>=p[i];j--)
		{
			int k=p[i];
			while (k<=j)
			{
				dp[j]=(dp[j]+dp[j-k]*k)%m;
				k=k*p[i]%m;
			}
		}
	for (int i=0;i<=n;i++)
		ans=(ans+dp[i])%m;
	cout<