D. Counting Arrays

题目描述：

给定数组a，你需要进行n次如下操作：

• 选择任意一个满足gcd(a[i],i)=1的下标i，将其放入b数组中，且从a数组中删除a[i]这个数字后，在i后面的所有数字左移

显然，b数组是a数组的操作方法

如果至少存在两种操作方法，则称a数组是牛逼的，现在给你n，a[i]可以是1到m中任意的数字，问存在多少种a数组是牛逼的，长度是1到n

思路：

逆向思维，我们要求操作方法>=2的数组，我们可以求操作方法=1的，然后用所有方案数去减去它

如何求一个长度是i的，且操作方法只有一种的数组的数量呢?

首先，无论数组的数字是什么，我们都一定存在一种操场方法是1 1 1 1 1 1...这样全是1的b数组，原因就是1和任何数的最大公约数是1，所以我们要保证再不存在别的方法使得a数组能被操作

介于上面的结论，我们要保证a数组的a[i]与1到i的所有数字都不互质，即gcd(a[i], j) != 1, 1<=j<=n，显然与1-i中所有数字互质的数字最小数是1-i中所有质数的乘积，我们计作x，显然x的倍数也满足条件，则1-m中与1-i所有数字都不互质的数的数量为m/x

显然，长度为i的要建立在长度为i-1的基础上，因为要保证前面每一位都是与前面那些j不互质，也就是连乘的关系

我们可以当成一个递推，dp[i]=dp[i-1]*(m/x)

当x足够大的时候，m/x就等于0了，那个时候直接dp[i]=0

当然这个题可以不用数组，直接用一个mul做变量连乘即可，快速幂也可以不用，直接用变量连乘过去

#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define inf 0x3f3f3f3f
#define mod7 1000000007
#define mod9 998244353
#define m_p(a,b) make_pair(a, b)
#define mem(a,b) memset((a),(b),sizeof(a))
#define io ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
typedef long long ll;
typedef pair <int,int> pii;

#define MAX 300000 + 50
ll n, m;
ll dp[MAX];

bool is_prime(ll n){
    if(n == 1)return false;
    for(int i = 2; 1ll * i * i <= n; ++i){
        if(n % i == 0)return false;
    }
    return true;
}
ll q_pow(ll a, ll b, ll mod){
    ll ans = 1;
    a%=mod;
    while(b > 0){
        if(b & 1)ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}

void work(){
    cin >> n >> m;
    ll fuck = 1ll;
    dp[0] = 1ll;
    ll ans = 0;
    for(ll i = 1; i <= n; ++i){
        if(fuck && is_prime(i)){
            fuck *= i;
            if(fuck > m)fuck = 0ll;
        }
        if(fuck)dp[i] = (dp[i - 1] * ((m/fuck)%mod9))%mod9;
        else dp[i] = 0;
        (ans += (q_pow(m, i, mod9)+(mod9-dp[i]))%mod9)%=mod9;
    }
    cout << ans << endl;
}


int main(){
    io;
    work();
    return 0;
}