F. Function!

题目：F. Function!

总结：对于b>=a,logb^a往上取，那么一定是1。那么就只需要考虑loga^b,q =sqrt(n),对于 q+1~n,每一段的答案都是 i*(n-i+1),可以将这个公式分解，就变成i*(n+1)-i²,对于i*(n+1)，可以用等差数列，对于i²,可以用n*(n+1)(2n+1)/6。 还有一种情况就是从1～n,他们之间有成倍数的关系。可以推算出来。特别需要注意模除。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e6+10;
const ll mod = 998244353;


ll ksm(ll a,ll b){
    ll ans = 1;
    while(b){
        if(b&1) ans = (ans*a)%mod;
        b >>= 1;
        a = (a*a)%mod;
    }
    return ans%mod;
}
ll solve(ll t,ll n){
    ll ans = (((((((n-t)%mod)*((t+1+n)%mod))%mod)*ksm(2,mod-2))%mod)*((n+1)%mod)+mod)%mod;
    ll cnt = (((((n%mod*((n+1)%mod))%mod*((2*n+1)%mod))%mod-((t*(t+1))%mod*((2*t+1)%mod)+mod)%mod)%mod*ksm(6,mod-2))%mod+mod)%mod;
    return (ans-cnt+mod)%mod;
}
int main(){
    ll n;
    cin >> n;
    ll ans = 0;
    ll q = sqrt(n);
    for(ll i = 2;i <= q;i++){
        ll p = 1,s = i,j = i*i;
        ll t = j-1;
        while(t <= n){
            ans = (ans+((((t-s+1))%mod*i)%mod*p)%mod)%mod;
            p++;
            s = t+1;
            j *= i;
            t = j-1;
        }
        if(s <= n){
            ans = (ans+(((n-s+1))%mod*i*p)%mod)%mod;
        }

    }
    cout<<(ans+solve(q,n)+mod)%mod<<endl;
    return 0;
}