LOJ 6714 Stupid Product

LOJ 6714 Stupid Product

定义一个序列为 (prod_{i} a_i(a_i>1))，空序列的权值为 (1)

记权值为 (x) 的序列个数为 (f(x))

给定 (n)，求 (sum^n f(x))

(nle 10^{10})，答案对 (998244353) 取模。

Solution

不难发现 (f(1)=1,f(x)=sum_{d|x,d e x} f(d))

考虑迪利克雷卷积意义下的 (fcdot I)，有：

对于 (x=1,fcdot I(1)=1)

对于 (x e 1,fcdot I(x)=2f(x))

对于 (S(n)=sum_{i=1}^n f(i)) 考虑

[2S(n)-1=sum_{i=1}^{n}sum_{j|i}f(j) ]

[2S(n)-1=sum_{j=1}^n sum_{kle frac{n}{j}} f(k) ]

[2S(n)-1=sum_{j=1}^n S(Biglfloorfrac{n}{j}Big floor) ]

[S(n)=1+sum_{j=2}^n S(Biglfloorfrac{n}{j}Big floor) ]

直接递归就很对？复杂度 (mathcal O(n^{frac{3}{4}}))。

如果常数不好就会被卡掉，要写 (mathcal O(n^{frac{2}{3}}log^{w} n)) 之类的东西，不过我把取模删了就过了。

(Code:)

#include<bits/stdc++.h>
using namespace std ;
#define int long long
int gi() {
	char cc = getchar() ; int cn = 0, flus = 1 ;
	while( cc < '0' || cc > '9' ) {  if( cc == '-' ) flus = - flus ; cc = getchar() ; }
	while( cc >= '0' && cc <= '9' )  cn = cn * 10 + cc - '0', cc = getchar() ;
	return cn * flus ;
}
const int P = 998244353 ; 
const int M = 3e5 + 5 ; 
int n, lim, st[M], top, f1[M], f2[M] ; 
int S(int x) { return ( x <= lim ) ? f1[x] : f2[n / x] ; }
signed main()
{
	n = gi(), lim = sqrt(n) + 1 ; 
	for(int l = 1, r; l <= n; l = r + 1) 
		r = (n / (n / l)), st[++ top] = n / l ;
	f1[1] = 1 ; 
	for(int i = top - 1; i >= 1; -- i) {
		int x = st[i], ans = 1 ;
		for(int l = 2, r; l <= x; l = r + 1) {
			r = (x / (x / l)) ;
			ans = (ans + (r - l + 1) * S(x / l)) ; 
		} ans %= P ; 
		if( x <= lim ) f1[x] = ans ;
		else f2[n / x] = ans ; 
	}
	cout << f2[1] << endl ; 
	return 0 ;
}