题目链接
解析
首先 \(A\) 中的数必定是 \(N\) 的约数，通过暴搜可以求出一个小于等于 \(10^{10}\) 的数最多只会有 \(2304\) 个约数。
由于题目要求 \(A\) 中的数互不相同，而 \(13!<10^{10}<14!\)，所以 \(A\) 中至多有 \(13\) 个数。
于是可以考虑 DP。设 \(f_{i,j,k}\) 表示考虑了前 \(i\) 个约数，选了 \(j\) 个数，乘积为第 \(k\) 个约数的方案数；类似地，设 \(g_{i,j,k}\) 表示这些方案的 \(A\) 中元素和。如果设 \(d_i\) 表示 \(N\) 的第 \(i\) 个约数，那么：
若 \(d_i \mid d_k\)，则有选/不选第 \(i\) 个约数，这两种情况，若选，则有 \(j\) 个位置可以插入：
\[f_{i,j,k} = f_{i - 1,j,k} + f_{i - 1,j - 1,get_{i,k}} \cdot j
\\
g_{i,j,k} = g_{i - 1,j,k} + g_{i - 1,j - 1,get_{i,k}} \cdot j+ f_{i - 1,j - 1,get_{i,k}} \cdot d_i \cdot j
\]
其中 \(get_{i,k}\) 表示 \(\frac{d_k}{d_i}\) 等于第几个约数。
否则，无法选取 \(d_i\)：
\[f_{i,j,k} = f_{i - 1,j,k}
\\
g_{i,j,k} = g_{i - 1,j,k}
\]
若令 \(d(N)\) 表示 \(N\) 的约数个数，则时间复杂度为 \(O(d(N) ^ 2)\)。
代码
/*
*/
#include <bits/stdc++.h>
#define eps 0.0000000001
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int N = 3000 + 5,M = 14,P = 2000000,mod = 998244353;
int f[N][M][N],g[N][M][N];
int gt[N][N];
signed main(){ios::sync_with_stdio(false);cin.tie(0),cout.tie(0);
// freopen("in.txt","r",stdin);
// freopen("out.txt","w",stdout);memset(gt,-1,sizeof(gt));ll n;cin>>n;vector<ll> d;d.push_back(-1);for(int i=1;1ll * i * i<=n;i++){if(n % i == 0){d.push_back(i);if(1ll * i * i != n){d.push_back(n / i);}}}sort(d.begin(),d.end());for(int i=1;i<d.size();i++){for(int j=i;j<d.size();j++){if(d[j] % d[i] == 0){gt[i][j] = lower_bound(d.begin(),d.end(),d[j] / d[i]) - d.begin();}}}f[0][0][1] = 1;for(int i=1;i<d.size();i++){for(int j=0;j<M;j++){for(int k=1;k<d.size();k++){f[i][j][k] = f[i - 1][j][k];g[i][j][k] = g[i - 1][j][k];if(d[k] % d[i] == 0 && j){f[i][j][k] = (1ll * f[i - 1][j - 1][gt[i][k]] * j % mod + f[i][j][k]) % mod;g[i][j][k] = ((1ll * f[i - 1][j - 1][gt[i][k]] * j % mod * (d[i] % mod) % mod + 1ll * g[i - 1][j - 1][gt[i][k]] * j % mod) % mod + g[i][j][k]) % mod;} }}}int res = 0;for(int i=0;i<M;i++){res = (res + g[d.size() - 1][i][d.size() - 1]) % mod;}cout<<res;return 0;
}