数论-整除分块

好久没碰数论的东西了，已经完全生疏了。

做了几道数论题总结一下。

余数求和

大意：
求 

思路：
隐约记得哪次比赛做过原题，也做出来了，但是现在还是有点懵了。。。

先把式子转化一下吧

那么整个式子就稍微有点样子了。

接下来对每一个l求对应的r

令，

r=max(i),i*t<=n;

得到：

r=k/t；

这是对于每一个l对应的r，对于里面的,i在连续的区间里是一个等差数列，那么直接套公式即可。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define mx *max_element 
const ll N=2e5+10;
ll n,k,r;
int main()
{ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	cin>>n>>k;
	ll ans=n*k;
	for(int l=1;l<=n;l=r+1)
	{
		ll t=k/l;
		if(t!=0) r=min(k/t,n);
		else r=n;
		ans-=t*(r-l+1)*(l+r)/2;
	}
	cout<<ans<<endl;
	return 0;
}

虽然是一道省选-，但代码是真的短。

calculating

大意：

思路：
首先，这个就是求，也就是我们所熟知的求数字约数的函数，换句话说，这里,其中.

不妨做一个转换，改为先枚举d，则

,

到这一步，要求f（x）那就是轻而易举了。

最后,由于i是从l到r，那么，这样的话写一个函数就好了。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=998244353;
ll a,b;
ll f(ll x)
{
	ll ans=0;
	ll l,r;
	for(ll l=1;l<=x;l=r+1)
	{
		r=x/(x/l);
		ans=(ans+(x/l)*(r-l+1)%mod)%mod;
	}
	return ans%mod;
}
int main()
{
	cin>>a>>b;
	cout<<(f(b)-f(a-1)+mod)%mod<<endl;
	return 0;
}

点是有点多，但都想到了就挺板的。

模积和

大意：

思路:
这里有一个限制是i！=j，所以不妨把式子转化一下。

 其中

这个就是我们在第一个问题里讨论的东西，那应该就很好处理了。

然后是后面的东西，如果展开的话：

这里的第一项就不用说了，第二三项其实跟上面讨论的是一个道理，只是加了一个常数而已。

那么最后一项，，与上一个的区别只是i的次数提高了一项，但如果照搬之前的思路，求等差数列的和的话，,那么这一项也解决了，那么整个题目到这里也就ok了。

还想说一个坑点，就是题目里这个取模的数居然不是质数。。。

也怪我傻，998244353，1e9+7见多了，看啥都像质数

所以这里的逆元得自己提前去求好了，不能用快速幂。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll mod=19940417;
const ll inv2=9970209;
const ll inv6=3323403;
#define endl '\n'
ll n,m;
ll sd(ll x)
{
	return x*(x+1)%mod*(2*x+1)%mod*inv6%mod;
}
ll sdd(ll x)
{
	return x*(x+1)%mod*inv2%mod;
}
ll f(ll n)//求sum(n-(n/i)*i) 
{
	ll sum=n*n%mod;
	//cout<<sum<<endl;
	for(ll l=1,r;l<=n;l=r+1)
	{
	    ll t=n/l;
	    r=n/t;
	    sum=(sum-t*(sdd(r)-sdd(l-1)+mod)%mod+mod)%mod;
	    //cout<<sum<<endl;
	} 
	return sum;
}
int main()
{
	cin>>n>>m;
	//cout<<sdd(4)<<' '<<sdd(3)<<endl;
	//cout<<f(n)<<" "<<f(m)<<endl;
	ll sum=0,ans=0;
	sum=(sum+f(n))%mod;
	sum=(sum*f(m))%mod;
	ans=sum;sum=0;
	for(ll l=1,r;l<=min(n,m);l=r+1)
	{
		r=min(n/(n/l),m/(m/l));
		sum+=(r-l+1+mod)%mod*n%mod*m%mod;
		sum-=(r-l+1+mod)%mod*(l+r)%mod*((n/l)*m%mod+(m/l)*n%mod)%mod*inv2%mod;
		sum+=(sd(r)-sd(l-1)+mod)%mod*(n/l)%mod*(m/l)%mod;
		sum=(sum+mod)%mod; 
	}
	cout<<(ans-sum+mod)%mod<<endl;
	return 0;
}

大致就先这样，后面可能会补新的题