Number theory blocking (integer division blocking)

Preface ：

Break for too long , I forgot how to blog ..
This blog is used to introduce a quick solution with integral Division .
 

Symbol description :

$\lfloor \frac{a}{b}\rfloor$ ：$a$ Divide $b$ Rounding down .
$\lceil \frac{a}{b}\rceil$ ：$a$ Divide $b$ Rounding up .
${\sum }_{i=1}^{n}f(i)$  ： Cumulative sign , Express $f(1)+f(2)+\dots +f(n)$.
 
 

problem ：

solve ${\sum }_{i=1}^n\lfloor \frac{n}{i}\rfloor$, among $1⩽n⩽1e12$.
 

Text ：

First , It's not hard to find one o(n) The violence of .
We need a $\sqrt{n}$ How to do it .
 
Let's take an example , Let's take $n=10$, Then enumerate from $1$ To $n$ enumeration $i$, Observe $\lfloor \frac{n}{i}\rfloor$ Value .
 

$1$   $2$   $3$   $4$   $5$   $6$   $7$   $8$   $9$   $10$

$10$ $5$   $3$   $2$   $2$   $1$   $1$   $1$   $1$   $1$

 
That's what it looks like up there .
It's not hard to find or prove , The same number is continuous , It can be divided into segments with the same value . Then we can use this property , For each piece , Multiply the number of this block by the length of the block , You can solve the sum of this block .
 
There are still two problems to be solved .
One is Number of blocks , One is How to quickly find both ends of a block .
 
First, the number of blocks , about $i$ from $1$ To $n$ Value ,$\lfloor \frac{n}{i}\rfloor$ The number of values of will not exceed $2\sqrt{n}$, That is, the number of blocks will not exceed $2\sqrt{n}$.
It's easy to prove ,
Um. , It can be proved , front $\sqrt{n}$ individual $i$ At most $\sqrt{n}$ Seed value , And when $i$ Greater than $\sqrt{n}$ when , The value must be less than $\sqrt{n}$, So no more than $2\sqrt{n}$（ Excerpt from ztc Mouth paste ）.

 
So the second question is , Quickly find the endpoint of the block .
When the left end point of a piece is $l$, So its right endpoint $r$ Namely $\lfloor \frac{n}{\lfloor \frac{n}{l}\rfloor }\rfloor$. This is even better proof .
It can also be interpreted as , It is known that $i$, Then with $i$ The right endpoint of the same block is $\lfloor \frac{n}{\lfloor \frac{n}{i}\rfloor }\rfloor$
in other words , When $i$ The value is $l$ To $r$ Between time , The result of the formula is the same , So just multiply by the length of the interval $(r-l+1)$ that will do .

Finally, for the original problem , Upper template code ：( If there is mold taking, add mold taking )

ll ans=0;
for(ll l=1,r;l<=n;l=r+1)
{
    
	r=n/(n/l);
	ans+=(r-l+1)*(n/l);
}

 
 

Examples and applications ：

A few more examples , Yes , But not all , I still need to find more questions to do .

problem 1：

It is known that $w$ and $n$, solve ${\sum }_{i=1}^n\lfloor \frac{w}{i}\rfloor$, among $1⩽n,w⩽1e12$.

Explain ：

Different from the original question , The upper bound of enumeration here $n$ No longer as a divisor .
So when calculating the right endpoint $r$ When , It will cause a detailed problem .
Look at the formula ,$r=w/(w/l)$. There are two special situations .
One is $w/l==0$, At this point, calling this formula again will lead to division $0$ The situation of , Lead to RE.
The other is , The result of the calculation is $r>n$, At this time, the right endpoint is not within the boundary .
Take these two situations into account , Modify on the basis of the original code .

ll ans=0;
for(ll l=1,r;l<=n;l=r+1)
{
    
	if(w/l)r=w/(w/l);
	else r=n;
	r=min(r,n);
	ans+=(r-l+1)*(w/l);
}

 
 

problem 2：

It is known that $a,b$ and $n$, solve ${\sum }_{i=1}^n\lfloor \frac{a}{i}\rfloor \lfloor \frac{b}{i}\rfloor$, among $1⩽n,a,b⩽1e12$.

Explain ：

Multiply the original problem by one more , But don't be afraid. , Just from the original $2\sqrt{a}$ A breakpoint , Turned into $2\sqrt{a}+2\sqrt{b}$ A breakpoint , Complexity is still at the root level .
We just need to find the nearest breakpoint every time .

ll ans=0;
for(ll l=1,r,r1,r2;l<=n;l=r+1)
{
    
	if(a/l)r1=a/(a/l);
	else r1=n;
	if(b/l)r2=b/(b/l);
	else r2=n;
	r=min(r1,r2)
	r=min(r,n);
	ans+=(r-l+1)*(a/l)*(b/l);
}

 
 

problem 3：

It is known that $w$ and $n$, solve ${\sum }_{i=1}^n\lceil \frac{w}{i}\rceil$, among $1⩽n,w⩽1e12$.

Explain ：

This is rounded up , It's hard to find the same conclusion as before , But we can convert rounding up to rounding down .
$\lceil \frac{w}{i}\rceil =\lfloor \frac{w+i-1}{i}\rfloor =\lfloor \frac{w-1}{i}\rfloor +1$
It's easy to solve .

ll ans=0;
for(ll l=1,r;l<=n;l=r+1)
{
    
	if((w-1)/l)r=(w-1)/((w-1)/l);
	else r=n;
	r=min(r,n);
	ans+=(r-l+1)*((w-1)/l+1);
}

 
 

problem 5：

It is known that $w$ and $n$, solve ${\sum }_{i=1}^{n}i\lfloor \frac{w}{i}\rfloor$, among $1⩽n,w⩽1e12$.

Explain ：

One more $i$, The difference from the original is , We can't take... This time $r-l+1$ 了 , front $r-l+1$ The essence of is actually the interval and , What we're going to multiply by is the interval $i$ Sum of .（ Because in this interval $\lfloor \frac{w}{i}\rfloor$ It's the same , Equivalent to a constant coefficient , That's why I can take it like this ）

ll ans=0;
for(ll l=1,r;l<=n;l=r+1)
{
    
	if(w/l)r=w/(w/l);
	else r=n;
	r=min(r,n);
	ans+=(r-l+1)*(l+r)/2*(w/l);
}

 
 

problem 6： Module sum product

seek ${\sum }_{i=1}^n{\sum }_{j=1}^m(nmodi)\times (mmodj),i\ne j$ model $19940417$ Value .
among $1⩽n,m⩽1e9$.

Explain ：

The first thing to know is $(nmodi)=n-i\times \lfloor \frac{w}{i}\rfloor$.
Then we start to change the formula , Be careful $i\ne j$ The condition of cannot be ignored .

After the formula is formulated , You can write .

#include<bits/stdc++.h>
#include<unordered_map>
using namespace std;
typedef long long ll;
const ll mod=19940417;
typedef pair<int,int> P;
const ll MAXN=1000000;

const ll inv6=3323403;
ll sum(ll l,ll r,ll flag)
{
    
    if(flag==1)
    {
    
        return (r-l+1)*(l+r)/2%mod;
    }
    else
    {
    
        return (r*(r+1)%mod*(2*r+1)%mod*inv6%mod-(l-1)*l%mod*(2*l-1)%mod*inv6%mod+mod)%mod;
    }
}

int main()
{
    
    ll n,m;
    scanf("%lld%lld",&n,&m);
    ll sum1=0;
    for(ll l=1,r;l<=n;l=r+1)
    {
    
        r=n/(n/l);
        sum1=(sum1+n*(r-l+1)%mod-sum(l,r,1)*(n/l)%mod+mod)%mod;
    }
    ll sum2=0;
    for(ll l=1,r;l<=m;l=r+1)
    {
    
        r=m/(m/l);
        sum2=(sum2+m*(r-l+1)%mod-sum(l,r,1)*(m/l)%mod+mod)%mod;
    }
    ll nm=min(n,m);
    ll sum3=0;
    for(ll l=1,r,r1,r2;l<=nm;l=r+1)
    {
    
        if(n/l)r1=n/(n/l);
        else r1=nm;
        if(m/l)r2=m/(m/l);
        else r2=nm;
        r=min(r1,r2);
        r=min(r,nm);
        sum3=(sum3+n*m%mod*(r-l+1)%mod-(n*(m/l)%mod+m*(n/l)%mod)*sum(l,r,1)%mod+sum(l,r,2)*(n/l)%mod*(m/l)%mod+mod)%mod;
    }
    ll ans=(sum1*sum2-sum3+mod)%mod;
    printf("%lld\n",ans);
    return 0;
}

 
 

problem 7： Sum the remainder

Explain ：

problem 6 Simplified version of , I won't post the code .