2019 ICPC 银川 Function（补题）数论分块+数学

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

题目链接 https://nanti.jisuanke.com/t/42386

推导过程（由于Latex太麻烦就直接板书）


AC代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
ll get_inv(ll dishu,ll zhishu)//a,p-2,,p是mod 
{ll ans=1;while(zhishu){if(zhishu&1){zhishu--;ans=ans*dishu%mod;}else{zhishu>>=1;dishu=dishu*dishu%mod;}}return ans;
}
int main()
{ll n;cin>>n;ll sn =sqrt(n);ll ans=(n+1)%mod*((n-sn)%mod)%mod*((n+sn+1)%mod)%mod*get_inv(2,mod-2)%mod;ans=(ans%mod+mod)%mod;ans=ans-(n%mod)*((n+1)%mod)%mod*((2*n+1)%mod)%mod*get_inv(6,mod-2)%mod;ans=(ans%mod+mod)%mod;ans=ans+(sn%mod)*((sn+1)%mod)%mod*((2*sn+1)%mod)%mod*get_inv(6,mod-2)%mod;ans=(ans%mod+mod)%mod;for(ll i=2;i<=sn;i++){ll sum=0;ll x=1;ll begin = pow(i,x);while(begin<=n){ll end=pow(i,x+1)-1;if(end>n){sum=(sum+(n-begin+1)%mod*x%mod)%mod;}else{sum=(sum+(end-begin+1)%mod*x%mod)%mod;}x++;begin = pow(i,x);}ans=(ans+sum*i%mod)%mod;}ans=(ans%mod+mod)%mod;cout<<ans;return 0;
}

如果鄙人的博客能够让你有哪怕一点点的收获，都是鄙人最大的荣幸，鄙人厚着脸皮向您讨个点赞，谢谢。

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

---