2019银川区域赛-F(取模不注意，AC两行泪)

题面

思路

这道题显示是要求前缀和，观察一下1-8的排列，显然发现如果一个数$a_i=p^k$也就是仅有一个素因子，那么响应的因子肯定会在这里有一个断点也就是会加一

我们看当n=8时

n=2 时 有2:1 ans=2*1=2

n=3 时 有2:1+1 3:1 ans = 2*2+3

n=4 时 有2:1+1+2 3:1 4:1 ans = 4*2+3+4

$\cdots$

n=8 时 有2:1+1+2+2+2+2+3;$\cdots$

先考虑n=8时对所有的贡献，
显然2从2~8都有1的贡献，也即是2(8-2+1)，枚举3~8得到
2(8-2+1)+3(8-3+1)+$\cdots$+8(8-8+1).
这个式子我们单独拆开来看

$$\begin{aligned} &x*(n-x+1)\\ =&x*(n+1)-x^2;对这个式子求和\\ =&\frac{n(n+1)^2}{2}-(n+1)-\frac{n(n+1)(2n+1)}{6}-1;因为从第二项开始，要减去1,痛分后得到\\ =&\frac{n(n+1)(n+2)}{6}-n \end{aligned}$$

得到最后的式子后，我们对考虑前面的贡献，显然每个数的平方或者立方都对后面造成了贡献，例如，当我们计算2的额外时，我们可以考虑它的平方4，那么2的贡献就多了(8-4+1)，再考虑8，贡献多了(8-8+1)，对于3也是如此，当$n>3^k$时，贡献就多了$3*(n-3^k+1)$,这样我们就能$\sqrt(n)$处理答案了

PS:打题的时候没考虑炸范围的问题，所以导致这题最后没过，记下这个锅

#include<bits/stdc++.h>
using namespace std;
#define ll long long 
const int md = 998244353;
ll ksm(ll x,ll y)
{   ll res=1;
	while(y)
	{
		if(y&1)res=(res*x)%md;
		y>>=1;
		x=(x*x)%md;
	}
	return res;
}
int main()
{
	ll n;
	scanf("%lld",&n);
	int sq =ceil(sqrt(n)); 
	ll ans = ((n%md*((n+1)%md))%md*(n%md+2)%md)%md;
    //取模的时候*号与%号运算级别相同所以得加括号
	ans=(ans*(ksm(6,md-2)))%md;
	ans=(ans-n+md)%md;
	for(ll i=2;i*i<=n;i++)
	{
		ll x=i*i; //这里如果i不是ll，需要加1ll*
		while(x<=n)
		{
			ans=(ans+(1ll*i*(n-x+1)))%md;
			x*=i;
		}
	}
	cout<<ans<<endl;
}