2019 ICPC银川 F Function!（数学分块+推公式）

本文主要是介绍2019 ICPC银川 F Function!（数学分块+推公式），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

思路：
思路来自https://blog.csdn.net/qq_43590432/article/details/103396063

在 a ≤ sqrt(n)的时候可以分块的计算，a > sqrt(n)的时候，后面的log变成了1，之后的部分推完公式直接O(1)算出来。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>using namespace std;typedef long long ll;const ll mod = 998244353;
ll n;ll qpow(ll x,ll m)
{ll res = 1;while(m){if(m & 1)res = (res * x) % mod;x = x * x % mod;m >>= 1;}return res;
}ll solve(ll x)
{ll x1 = (1 + x) * x % mod * qpow(2,mod - 2) % mod * (n % mod + 1) % mod;ll x2 = x * (1 + x) % mod * (2 * x % mod + 1) % mod * qpow(6,mod - 2) % mod;return (x1 - x2 + mod) % mod;
}int main()
{scanf("%lld",&n);ll mx = sqrt(n) + 1;ll ans = 0;for(int i = 2;i <= mx;i++){ll cnt = 1,k = i;for(ll j = i;j <= n;j = k){k *= i;if(k <= n + 1){ans = (ans + (k - j) % mod * i % mod * cnt % mod) % mod;}else{ans = (ans + (n + 1 - j) % mod * i % mod * cnt % mod) % mod;}cnt++;}}printf("%lld\n",(ans + solve(n % mod) - solve(mx % mod) + mod) % mod);return 0;
}

这篇关于2019 ICPC银川 F Function!（数学分块+推公式）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---