我的解法

这道题目的时间限制为 $2$ 秒，空间限制为 $1\ \mathrm{GB}$。

注意数据范围，可知我们需要一个线性复杂度。

我们可以设 $a_n=k$，那么我们就有 $k\mid a_i\ (1\le k\le n)$，那我们不妨得到一个新的数列 $b$ 使得 $b_i=\frac{a_i}{k}$。

那么原本的问题就转化为了 $b_n=1$ 且 $b_{i+1}\mid b_i\ (1\le i<n)$ 且 $1\le b_1\le \left \lfloor \frac{c}{k}\right \rfloor$。

那么，由于 $b_n=1$，我们只需要考虑剩下 $n-1$ 个数即可，易见 $b_1$ 为 $b$ 数列中其它所有数的倍数，我们不妨考虑，将 $b_n$ 分解为 $n-1$ 个数的乘积。

我们假设 $\mathrm{f}(x)$ 代表将 $x$ 分解为 $n-1$ 个数的乘积的方案数。

那么，我们简化后的问题的答案就为：

$$\sum_{i=1}^{\left \lfloor \frac{c}{k} \right \rfloor }\mathrm{f}(i)$$

然后，由于我们上面的 $k$ 的范围为 $1\le k\le c$，所以最后的答案就是：

$$\sum_{i=1}^{c}\sum_{j=1}^{\left \lfloor \frac{c}{i} \right \rfloor }\mathrm{f}(j)$$

那么问题就变成了，用线性复杂度求出 $\mathrm{f}(x)$ 的大小，把这个问题解决了，其它就都好办了。

我们考虑分解 $x$：

$$x=\prod_{i=1}^{m}p_i^{\alpha_i}$$

那么，我们使用插板法即可得到：

$$\mathrm{f}(x)=\prod_{j}\begin{pmatrix} \alpha_j+n-2 \\n-2 \end{pmatrix}$$

然后，我们应该时可以证明 $\mathrm{f}(x)$ 为积性函数的。

具体的，我们需要证明当 $\gcd(a,b)=1$ 时，$\mathrm{f}(a\times b)=\mathrm{f}(a)\times \mathrm{f}(b)$。

我们考虑 $\mathrm{f}(a\times b)$ 这个函数的值为 $\prod_{i=1}^{n-1}c_i=a\times b$ 的 $k$ 元组 $(c_1,c_2,\dots,c_{n-1})$ 的数量。

由于 $\gcd(a,b)=1$ 所以我们可以唯一分解 $c_i=d_i\times e_i$，并且 $d_i\mid a,e_i\mid b$ 且 $\gcd(d_i,e_i)=1$，则：

$$\prod_{i=1}^{n-1}c_i=\prod_{i=1}^{n-1}(d_i\times e_i)=\left(\prod_{i=1}^{n-1}d_i\right)\times \left(\prod_{i=1}^{n-1}e_i\right)=a\times b$$

接下来，我们只需要证明 $\prod_{i=1}^{n-1}d_i=a,\prod_{i=1}^{n-1}e_i=b$ 即可。

我们取任意质数 $p$：

• 若 $p\mid a$，则 $p\nmid b$，此时 $v_p(a\times b)=v_p(a)+v_p(b)=v_p(a)$，又因为 $v_p(c_i)=v_p(d_i)+v_p(e_i)$，但是 $e_i\mid b$ 所以 $v_p(e_i)=0$，所以 $v_p(c_i)=v_p(d_i)$，因此：

$$v_p\left(\prod_{i=1}^{n-1}d_i\right)=\sum_{i=1}^{n-1}v_p(d_i)=\sum_{i=1}^{n-1}v_p(c_i)=v_p(ab)=v_p(a)$$

• 若 $p\mid b$，与上面同理可得 $v_p\left(\prod_{i=1}^{n-1}e_i\right)=v_p(b)$。
• 若 $p\nmid a\times b$，那么 $v_p\left(\prod_{i=1}^{n-1}d_i\right)=0=v_p(a),v_p\left(\prod_{i=1}^{n-1}e_i\right)=0=v_p(b)$。

所以，对于所有的质数 $p$，都有 $v_p\left(\prod_{i=1}^{n-1}d_i\right)=v_p(a)$ 和 $v_p\left(\prod_{i=1}^{n-1}e_i\right)=v_p(b)$，所以 $\prod_{i=1}^{n-1}d_i=a,\prod_{i=1}^{n-1}e_i=b$。

然后，这道题目就好做了，我们考虑使用线性筛求 $\mathrm{f}(x)$，我们考虑两种情况当前的数为 $i$，质数为 $p_i$。

若 $p_i\mid i$，则我们推一下式子，就是我们设 $i=p_i^k\times m$ 那么现在的 $i\times p_i=p_i^{k+1}\times m$，我们用我们上面的表达式写出来，也就是 $\mathrm{f}(i)=\begin{pmatrix}k+n-2\\n-2\end{pmatrix}\times \mathrm{g}_{m},\mathrm{f}(i\times p_i)=\begin{pmatrix}k+n-1\\n-2\end{pmatrix}\times \mathrm{g}_{m}$，我们那么我们将这两个式子做比，就能得到：

$$\frac{\mathrm{f}(i\times p_i)}{\mathrm{f}(i)}=\frac{\begin{pmatrix}k+n-1\\n-2\end{pmatrix}}{\begin{pmatrix}k+n-2\\n-2\end{pmatrix}}=\frac{k+n-1}{k+1}$$

所以，我们可以得到 $\mathrm{f}(i\times p_i)=\mathrm{f}(i)\times\frac{k+n-1}{k+1}$，这里我们用乘法逆元做就可以了。

第二种情况就是，若 $p_i\mid i$ 那么，由于 $\mathrm{f}(x)$ 为积性函数，所以 $\mathrm{f}(i\times p_i)=\mathrm{f}(i)\times \mathrm{f}(p_i)$。

然后，这道题目就基本做完了，我们只需要再加一点细节就够了。

关于积性函数证明中的解释

我们的证明过程中出现了一种符号，叫做 $p$ 进赋值，它的定义为 $v_p(x)=\max\left\{k\in \mathbb{N}_0\ |\ p^k\mid x \right\}$，其中 $\mathbb{N}_0$ 代表非负整数集。

它有一个性质：

• 若 $p\nmid x$，则 $v_p(x)=0$。
• 对于任意正整数 $a,b$ 和质数 $p$ 有 $v_p(a\times b)=v_p(a)+v_p(b)$。

还有一些性质，就不一一列举了，我们的证明中用到了如上两个性质。

参考代码

#include<bits/stdc++.h>
#define I using
#define AK namespace
#define IOI std
#define i_ak return
#define ioi  0
#define i_will signed
#define ak main
#define IMO ()
#define double long double
#define R register
#define fi first
#define se second
#define mem memset
#define rep(a,b,c) for(int a=b;a<=c;++a)
#define per(a,b,c) for(int a=b;a>=c;--a)
#define pb push_back
#define sort stable_sort
#define con continue
#define br break
#define Int Integer
I AK IOI;
class Integer{private:std::string value;public:Integer(void) = default;Integer(const int& x){value = std::to_string(x);}Integer(int&& x){value = std::to_string(x);x = 0;}Integer(const Integer& x){value = x.value;}Integer(Integer&& x) noexcept{if (&x != this){value = x.value;x.value = "";}}Integer(const std::string& x){value = x;}Integer(std::string&& x) noexcept{if (&x != &(this->value)){value = x;x = "";}}void operator=(const Integer& x){value = x.value;}void operator=(Integer&& x) noexcept{if (&x != this){value = x.value;x.value = "";}}const Integer operator+(const Integer& x) const{Integer all;all.value.resize(value.size() >= x.value.size() ? value.size() + 1 : x.value.size() + 1);int a = 0;bool more = false;while (a < (value.size() <= x.value.size() ? value.size() : x.value.size())){all.value[all.value.size() - a - 1] = (value[value.size() - a - 1] - '0') + (x.value[x.value.size() - a - 1] - '0') + (int)more + '0';more = false;if (all.value[all.value.size() - a - 1] > '9'){all.value[all.value.size() - a - 1] -= 10;more = true;}a++;}while (a < value.size()){all.value[all.value.size() - a - 1] = (value[value.size() - a - 1] - '0') + (int)more + '0';more = false;if (all.value[all.value.size() - a - 1] > '9'){all.value[all.value.size() - a - 1] = all.value[all.value.size() - a - 1] - 10;more = true;}a++;}while (a < x.value.size()){all.value[all.value.size() - a - 1] = (x.value[x.value.size() - a - 1] - '0') + (int)more + '0';more = false;if (all.value[all.value.size() - a - 1] > '9'){all.value[all.value.size() - a - 1] = all.value[all.value.size() - a - 1] - 10;more = true;}a++;}if (more){all.value[0] = '1';}else{all.value.erase(all.value.begin());}return all;}void operator+=(const Integer& x){value = operator+(x).value;}void operator++(){value=operator+(1).value;}const Integer operator-(const Integer& x) const{Integer all;all.value.resize(value.size());int a = 0;bool less = false;while (a < (value.size() <= x.value.size() ? value.size() : x.value.size())){all.value[all.value.size() - a - 1] = (value[value.size() - a - 1] - '0') - (x.value[x.value.size() - a - 1] - '0') - (int)less + '0';less = false;if (all.value[all.value.size() - a - 1] < '0'){all.value[all.value.size() - a - 1] += 10;less = true;}a++;}while (a < value.size()){all.value[all.value.size() - a - 1] = (value[value.size() - a - 1] - '0') - (int)less + '0';less = false;if (all.value[all.value.size() - a - 1] < '0'){all.value[all.value.size() - a - 1] += 10;less = true;}a++;}while (all.value.size() > 1 && *all.value.begin() == '0'){all.value.erase(all.value.begin());}if (all.value.empty()){return (Integer)0;}else{return all;}}void operator-=(const Integer& x){value = operator-(x).value;}void operator--(){value=operator-(1).value;}const Integer operator*(const Integer& x) const{if (value == "0" || x.value == "0"){return (Integer)0;}Integer all;all.value.resize(value.size() + x.value.size(), '0');for (int a = value.size() - 1; a >= 0; a--){int more = 0;for (int b = x.value.size() - 1; b >= 0; b--){int total = (value[a] - '0') * (x.value[b] - '0') + (all.value[a + b + 1] - '0') + more;all.value[a + b + 1] = (total % 10) + '0';more = total / 10;}if (more){all.value[a] = (more + '0');}}while (!all.value.empty() && *all.value.begin() == '0'){all.value.erase(all.value.begin());}if (all.value.empty()){return (Integer)0;}else{return all;}}void operator*=(const Integer& x){value = operator*(x).value;}const Integer operator/(const Integer& x) const{Integer last = 0;std::string total = "";for (int a = 0; a < value.size(); a++){last = last * (Integer)10 + (Integer)(value[a] - '0');int count = 0;while (x * (Integer)count <= last){count++;}total += count - 1 + '0';last -= x * (Integer)(count - 1);}while (total.size() > 1 && *total.begin() == '0'){total.erase(total.begin());}return (Integer)total;}void operator/=(const Integer& x){value = operator/(x).value;}const Integer operator%(const Integer& x)const{Integer last = 0;std::string total = "";for (int a = 0; a < value.size(); a++){last = last * (Integer)10 + (Integer)(value[a] - '0');int count = 0;while (x * (Integer)count <= last){count++;}total += count - 1 + '0';last -= x * (Integer)(count - 1);}while (total.size() > 1 && *total.begin() == '0'){total.erase(total.begin());}return last;}void operator%=(const Integer& x){value = operator%(x).value;}bool operator<(const Integer& x) const{if (value.size() < x.value.size()){return true;}else if (value.size() > x.value.size()){return false;}else{return value < x.value;}}bool operator>(const Integer& x) const{if (value.size() > x.value.size()){return true;}else if (value.size() < x.value.size()){return false;}else{return value > x.value;}}bool operator<=(const Integer& x) const{if (value.size() < x.value.size()){return true;}else if (value.size() > x.value.size()){return false;}else{return value <= x.value;}}bool operator>=(const Integer& x) const{if (value.size() > x.value.size()){return true;}else if (value.size() < x.value.size()){return false;}else{return value >= x.value;}}bool operator==(const Integer& x) const{if (value.size() != x.value.size()){return false;}else{return value == x.value;}}bool operator!=(const Integer& x) const{if (value.size() != x.value.size()){return true;}else{return value != x.value;}}operator int(void) const{return std::stoi(value);}friend std::istream& operator>>(std::istream& stream, Integer& x){stream >> x.value;return stream;}friend std::ostream& operator<<(std::ostream& stream, const Integer& x){stream << x.value;return stream;}~Integer(void) = default;};namespace fastIO{char *p1,*p2,buf[100000];
	#define nc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++)
	inline void read(int&n){int x=0,f=1;char ch=nc();while(ch<48||ch>57){if(ch=='-'){f=-1;}ch=nc();}while(ch>=48&&ch<=57){x=(x<<3)+(x<<1)+(ch^48),ch=nc();}n=x*f;}inline void read(string&s){s="";char ch=nc();while(ch==' '||ch=='\n'){ch=nc();}while(ch!=' '&&ch!='\n'){s+=ch,ch=nc();}}inline void read(char&ch){ch=nc();while(ch==' '||ch=='\n'){ch=nc();}}inline void write(int x){if(x<0){putchar('-'),x=-x;}if(x>9){write(x/10);}putchar(x%10+'0');return;}inline void write(const string&s){for(R int i=0;i<(int)s.size();i++){putchar(s[i]);}}inline void write(const char&c){putchar(c);}
}using namespace fastIO;
const int INF=0x3f3f3f3f;
inline int gcd(int a,int b){if(a==0)return b;if(b==0)return a;int k;for(k=0;((a|b)&1)==0;k++){a>>=1;b>>=1;}while((a&1)==0)a>>=1;do{while((b&1)==0)b>>=1;if(a>b)swap(a,b);b=(b-a);}while(b!=0);return a<<k;}inline int lcm(const int&a,const int&b){return a*b/gcd(a,b);}
inline int pow(int a,int b){int res=1;while(b){if(b&1)res*=a;a*=a;b>>=1;}return res;}
inline int powmod(int a,int b,const int&mod){int res=1;a%=mod;while(b){if(b&1)res=res*a%mod;a=a*a%mod;b>>=1;}return res%mod;}
inline int lowbit(int x){return x&(-x);}
const int mod=998244353,N=50000005;
int inv[32],f[N],F[N],cnt[N],primes[N/10],n,c,tot,ans;
bool not_prime[N];
i_will ak IMO{
    cin>>n>>c;
    inv[1]=1;
    rep(i,2,31)inv[i]=(long long)(mod-mod/i)*inv[mod%i]%mod;
    f[1]=1;
    not_prime[1]=1;
    rep(i,2,c){
        if(!not_prime[i]){
            primes[++tot]=i;
            f[i]=n-1;
            cnt[i]=1;
        }
        for(int j=1;j<=tot&&(long long)i*primes[j]<=c;j++){
            int p=primes[j];
            not_prime[i*p]=1;
            if(i%p==0){
                cnt[i*p]=cnt[i]+1;
                int k=cnt[i];
                f[i*p]=(long long)f[i]*(k+n-1)%mod;
                f[i*p]=(long long)f[i*p]*inv[k+1]%mod;
                br;
            }
			else{
                cnt[i*p]=1;
                f[i*p]=(long long)f[i]*f[p]%mod;
            }
        }
    }
    rep(i,1,c)F[i]=(F[i-1]+f[i])%mod;
    rep(i,1,c)ans=(ans+F[c/i])%mod;
    cout<<ans;
    i_ak ioi;
}

亲测可过，请勿抄袭。