• 怎么搞？
• 设：

$$F(n,m)=\sum_{i=1}^m\varphi(n\cdot i)$$

• 考虑质数 $p|n$，根据性质分类讨论，可以得到公式：

$$F(n,m)=\begin{cases}F(n/p,m)\cdot p&p^2|n\\F(n/p,m)\cdot (p-1)+F(n,\lfloor m/p\rfloor)&\text{otherwise}\end{cases} $$

• 边界是 $n=1$ 时需要使用杜教筛。
• 状态数目前复杂度未知，但是它可过，跑得还挺快。

#include<bits/stdc++.h>
const int N=1100000,mod=998244353;
using namespace std;
int n,m,pr[N],phi[N];
unordered_map<int,int>res[N];
bool ok[N];
int f(int x,int y)
{
	if(!y)return 0;
	if(res[x].count(y))return res[x][y];
	if(x==1)
	{
		long long Phi=1ll*y*(y+1)/2;
		for(int l=2,r;l<=y;r=y/(y/l),Phi-=1ll*f(1,y/l)*(r-l+1),l=r+1);
		return res[1][y]=Phi%mod;
	}
	return res[x][y]=(ok[x]?1ll*f(x/pr[x],y)*(pr[x]-1)+f(x,y/pr[x]):1ll*f(x/pr[x],y)*pr[x])%mod;
}
int main()
{
	scanf("%d%d",&n,&m);
	int w=max(n,int(pow(m,2.0/3.0)));
	ok[1]=1,iota(phi,phi+w+1,0);
	for(int i=1;i<=w;++i)
		if(!ok[i])
			for(int j=i;j<=w;j+=i)
				pr[j]=i,ok[j]=1,phi[j]=phi[j]/i*(i-1);
	res[1][1]=1;
	for(int i=2;i<=w;++i)
		res[1][i]=(res[1][i-1]+phi[i])%mod,ok[i]=i%(1ll*pr[i]*pr[i]);
	long long ans=0;
	for(int i=1;i<=n;++i)ans+=f(i,m);
	printf("%lld",ans%mod);
	return 0;
} 

• 有谁能告诉我 $f(n,m)$（随便挑 $[1,n]$ 的质因子，可重复，满足积不大于 $m$ 的方案数）的渐进界，我就可以告诉你准确复杂度拉。