Number theory - division and blocking

I haven't touched number theory for a long time , It's completely rusty .

Made a few number theory problems to sum up .

Sum the remainder

Carelessness ：
seek  

Ideas ：
Vaguely remember which game did the original question , It's done, too , But now I'm still a little confused ...

Let's convert the formula first

So the whole equation is a little bit like .

Next for each l Find the corresponding r

Make ,

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

obtain ：

r=k/t;

This is for every one l Corresponding r, about Inside ,i In a continuous interval is a sequence of equal difference numbers , Then set the formula directly .

#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;
}

Although it is a provincial election -, But the code is really short .

calculating

Carelessness ：

Ideas ：
First , This Is o , That is, the well-known function of finding the divisor of numbers , let me put it another way , here , among .

You might as well make a conversion , Instead, enumerate first d, be

,

To this step , requirement f（x） That's easy .

Last , because i It's from l To r, that , In this case, write a function .

#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;
}

There are a lot of points , But when I think of it, it's very stiff .

Modular product sum

Carelessness ：

Ideas :
There is a limitation here i！=j, So we might as well convert the formula .

  among

This is what we discussed in the first question , That should be easy to handle .

Then there's the back , If it unfolds ：

The first item here goes without saying , The second and third items are actually the same as those discussed above It's one thing , Just add a constant .

So the last item ,, The difference from the previous one is i The number of times increased by one , But if you copy the previous ideas , Find the sum of the arithmetic sequence ,, So this one has been solved , So that's the whole topic ok 了 .

I also want to say a pit , The modular number in the title is not a prime number ...

Blame me for being stupid ,998244353,1e9+7 See more , Everything looks like prime numbers

So the inverse here has to be solved in advance , You can't use a fast power .

#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)// seek 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;
}

That's about it first , New questions may be added later