题解：P11253 [GDKOI2023 普及组] 小学生数学题

标签：return GDKOI2023 int 题解 friend operator Modint P11253 mod

所求的式子带除法，模意义下除法计算复杂度带 \(\log\) 太慢了，先改写成乘法：\(\sum_{i=1}^n i!\times i^{-k}\)。想求这个式子，最简单的思路就是对于每个整数 \(i\in[1,n]\)，分别预处理出 \(i!\) 和 \(i^{-k}\) 的值，最后乘起来再 \(O(n)\) 暴力加起来就好了！

对于 \(i!\)，注意到：

\[i!= \begin{cases} 1,&i=1\\ (i-1)!\times i,&i\ge 2\\ \end{cases} \]

可以直接 \(O(n)\) 递推。

对于 \(i^{-k}\)，注意到：

\[(ij)^{-k}=i^{-k}j^{-k} \]

因此 \(i^{-k}\) 是关于 \(i\) 的完全积性函数，且该函数进行单点求值的复杂度为 \(O(\log n)\)。\(n\) 以内质数个数是 \(O(\frac{n}{\log n})\) 的，暴力求质数处的点值之后，可以使用欧拉筛 \(O(n)\) 求出。

总复杂度 \(O(n)\)。

// Problem: P11253 [GDKOI2023 普及组] 小学生数学题
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P11253
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//By: OIer rui_er
#include <bits/stdc++.h>
#define rep(x, y, z) for(int x = (y); x <= (z); ++x)
#define per(x, y, z) for(int x = (y); x >= (z); --x)
#define debug(format...) fprintf(stderr, format)
#define fileIO(s) do {freopen(s".in", "r", stdin); freopen(s".out", "w", stdout);} while(false)
#define endl '\n'
using namespace std;
typedef long long ll;

mt19937 rnd(std::chrono::duration_cast<std::chrono::nanoseconds>(std::chrono::system_clock::now().time_since_epoch()).count());
int randint(int L, int R) {
    uniform_int_distribution<int> dist(L, R);
    return dist(rnd);
}

template<typename T> void chkmin(T& x, T y) {if(y < x) x = y;}
template<typename T> void chkmax(T& x, T y) {if(x < y) x = y;}

template<int mod>
inline unsigned int down(unsigned int x) {
	return x >= mod ? x - mod : x;
}

template<int mod>
struct Modint {
	unsigned int x;
	Modint() = default;
	Modint(unsigned int x) : x(x) {}
	friend istream& operator>>(istream& in, Modint& a) {return in >> a.x;}
	friend ostream& operator<<(ostream& out, Modint a) {return out << a.x;}
	friend Modint operator+(Modint a, Modint b) {return down<mod>(a.x + b.x);}
	friend Modint operator-(Modint a, Modint b) {return down<mod>(a.x - b.x + mod);}
	friend Modint operator*(Modint a, Modint b) {return 1ULL * a.x * b.x % mod;}
	friend Modint operator/(Modint a, Modint b) {return a * ~b;}
	friend Modint operator^(Modint a, int b) {Modint ans = 1; for(; b; b >>= 1, a *= a) if(b & 1) ans *= a; return ans;}
	friend Modint operator~(Modint a) {return a ^ (mod - 2);}
	friend Modint operator-(Modint a) {return down<mod>(mod - a.x);}
	friend Modint& operator+=(Modint& a, Modint b) {return a = a + b;}
	friend Modint& operator-=(Modint& a, Modint b) {return a = a - b;}
	friend Modint& operator*=(Modint& a, Modint b) {return a = a * b;}
	friend Modint& operator/=(Modint& a, Modint b) {return a = a / b;}
	friend Modint& operator^=(Modint& a, int b) {return a = a ^ b;}
	friend Modint& operator++(Modint& a) {return a += 1;}
	friend Modint operator++(Modint& a, int) {Modint x = a; a += 1; return x;}
	friend Modint& operator--(Modint& a) {return a -= 1;}
	friend Modint operator--(Modint& a, int) {Modint x = a; a -= 1; return x;}
	friend bool operator==(Modint a, Modint b) {return a.x == b.x;}
	friend bool operator!=(Modint a, Modint b) {return !(a == b);}
};

const int N = 2e7 + 5, mod = 998244353;
typedef Modint<mod> mint;

int n, k, tab[N], p[N], pcnt;
mint fac[N], invpw[N], ans;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> n >> k;
    fac[0] = fac[1] = 1;
    rep(i, 2, n) fac[i] = fac[i - 1] * i;
    tab[1] = 1;
    invpw[1] = ~(mint(1) ^ k);
    rep(i, 2, n) {
        if(!tab[i]) {
            p[++pcnt] = i;
            invpw[i] = ~(mint(i) ^ k);
        }
        for(int j = 1; j <= pcnt && i * p[j] <= n; ++j) {
            tab[i * p[j]] = 1;
            invpw[i * p[j]] = invpw[i] * invpw[p[j]];
            if(i % p[j] == 0) break;
        }
    }
    rep(i, 1, n) ans += fac[i] * invpw[i];
    cout << ans << endl;
    return 0;
}

标签：return,GDKOI2023,int,题解,friend,operator,Modint,P11253,mod
From： https://www.cnblogs.com/ruierqwq/p/18533851/LG-P11253