Location>code7788 >text

Number theory Möbius inversion

Popularity:662 ℃/2024-09-19 11:47:42

pre-conditioning

number theory subsection

conceptual

For someone who is shaped like a\(\sum_{x=1}^n \lfloor{\frac{n}{x}}\rfloor\) formulas, we find that for a portion of the\(x\)Their\(\lfloor{\frac{n}{x}}\rfloor\) The values are the same, so we don't need to\(\mathcal{O(n)}\) computation, a number-theoretic chunking approach can be used to reduce the complexity of this step to\(\mathcal{O(\sqrt{n})}\)

For a known value\(n\)Given a value\(l\)The variable is a variable that is used in the calculation.\(r\) The maximum value of makes:\(\lfloor{\frac{n}{l}}\rfloor=\lfloor{\frac{n}{r}}\rfloor\). It's better to draw conclusions that\(r=\lfloor{\frac{n}{\lfloor{\frac{n}{l}}\rfloor}}\rfloor\)

show that

image

Excerpted from OI-wiki.

appliance

It is usual in Mogul to divide\(n\) There's another one outside.\(m\) to form a double loop, for which we just need to change the\(r\) The location of the position makes it possible for the\(i\in \left[l,r\right]\) center\(\lfloor{\frac{n}{i}}\rfloor\) together with\(\lfloor{\frac{m}{i}}\rfloor\) It is sufficient that the value of is always the same. Provide that the\(n\le m\)

if(n>m) swap(n,m);
int res=0;
for(int l=1,r;l<=n;l=r+1)
{
	r=min(n/(n/l),m/(m/l));
	res=/*code*/;
}

linear sieve

One of the points of knowledge that must be used in the Mo Reverse.

First understand the Möbius function:

\[\mu(x)=\begin{cases} 1\qquad\quad n=1\\\\ 0 \qquad\quad n\, containing the square factor \\\ (-1)^k\quad k\, for \, n\, the number of essentially different prime factors \end{cases}\]

What you need to know, one, is that it is a product function, and two, how to sift through it linearly.

It is clear from the definition that\(\mu\) The value of the function is related to the primes, so while sifting it we need to sift the primes linearly.

simplest sieve

\(u\) because of\(\mu\) The value of the function, the\(N\) is an upper bound on the value domain, and the others are common to sieve prime numbers.

int u[N],pri[N],tot;
bool vis[N];
void Wprepare()
{
	u[1]=1;
	for(int i=2;i<=N;i++)
	{
		if(!vis[i]) pri[++tot]=i,u[i]=-1;
		for(int j=1;j<=tot;j++)
		{
			if(i*pri[j]>N) break;
			vis[i*pri[j]]=1;
			if(i%pri[j]==0) break;
			u[i*pri[j]]=-u[i];
		}
	}
}

Mo anti usually more measured.Mostly we need to prep some more values of other functions in the equation in preparation, and sometimes we have to do prefix sums and a bunch of other operations on them, all of which vary from question to question and require us to be flexible.

Some ability to push equations

how manyapparentVery common transformation of equations:

default (setting)\(n\le m\)

A little more basic:

  • \[Law of exchange \sum_x\sum\sum f(x)=\sum_x f(x)\sum\sum \]

  • \[Multiply and divide together, transform upper bound\sum_{i=1}^n\sum_{j=1}^m [gcd(i,j)=d]=\sum_{i=1}^{\lfloor{\frac{n}{d}}\rfloor}\sum_{j=1}^{\lfloor{\frac{m}{d}}\rfloor}[ gcd(i,j)=1] \]

  • \[Equivalent description, such that \,T=dx:\sum_{d=1}^n\sum_{x=1}^{\lfloor{\frac{n}{d}}\rfloor}=\sum_{T=1}^n \sum_{x|T} \]

Raise it a little:

  • \[Combined above\sum_{i=1}^n \sum_{j=1}^m f(gcd(i,j))=\sum_{d=1}^n f(d)\sum_{i=1}^{\lfloor{\frac{n}{d}}\rfloor} \sum_{j=1}^{\lfloor{\frac{m}{d}} \rfloor} \;[gcd(i,j)=1] \]

  • \[enumerate factors, de-loop\sum_{i=1}^n\sum_{j=1}^m\sum_{x|gcd(i,j)} \mu(x)=\sum_{x=1}^n \mu(x)\lfloor{\frac{n}{x}}\rfloor\lfloor{\frac{m}{x}}}\rfloor \]

  • Enumerating denominators to facilitate number-theoretic chunking
    honorific title\(T=dx\)

\[\begin{aligned} Ans &= \sum_{d=1}^n f(d) \sum_{x=1}^{\lfloor{\frac{n}{d}}\rfloor} \mu(x) \lfloor{\frac{n}{dx}}\rfloor \lfloor{\frac{m}{dx}}\rfloor \\ &= \sum_{T=1}^n \lfloor{\frac{n}{T}}\rfloor \lfloor{\frac{m}{T}}\rfloor \sum_{d|T} f(d) \mu(\frac{T}{d}) \end{aligned} \]

main part

Since Konjac doesn't know how to convolve or anything else, it only uses one of the most basic inversion formulas

The inversion formula:

\[[gcd(i,j)=1]=\sum_{d|gcd(i,j)} \mu(d) \]

This is introduced by a property of the Möbius function:

\[\sum_{d|n}=\begin{cases}1\quad n=1 \\ 0 \quad n\neq 1\end{cases} \]

The nature is proved as follows:

image

Excerpted from OI-wiki.

If you're like me and don't have too strong a desire to know about these types of formulas, then the serving method is as follows:

  • Based on the question, introduce Eq;
  • as far as possible\([gcd(i,j)=1]\) direction of the push and then use the inverse formula;
  • Combine the above transformation of equations to introduce an equation that can be preprocessed out of function values and can be optimized for complexity using number theory chunking, and thenAC Start tuning the code.

example

The key to doing Mo's inverse I think is just brushing up, finding commonalities in the constant pushing of equations, practice makes perfect.

Let's start with a recommendationlesson planThe above tips for pushing equations are all better in a step-by-step manner. Personally recommend a way to learn: the first few more basic questions can look at the solution of the formula to understand little by little, and then go back and try to independently complete their own push formula, and then to continuously optimize the sieve method.

The first few questions of the formula section will be written in a bit more detail, which may lead to lengthy please forgive me qwq.

Note: The following questions are unspecified as default\(n\le m\)

YY's GCD

This question, despite its position in the first question, is actually quite a lot to consider, combining almost all of the above techniques for pushing the formula.

\[\begin{aligned} Ans&= \sum_{i=1}^n\sum_{j=1}^m \;[gcd(i,j)\in prime] \\ &= \sum_{d=1}^n\sum_{i=1}^n\sum_{j=1}^m \;[gcd(i,j)=d]\;(d\in prime)\\ &= \sum_{d=1}^n\sum_{i=1}^{\lfloor{\frac{n}{d}}\rfloor}\sum_{j=1}^{\lfloor{\frac{m}{d}}\rfloor} \;[gcd(i,j)=1]\;(d\in prime)\\ &=\sum_{d=1}^n\sum_{i=1}^{\lfloor{\frac{n}{d}}\rfloor}\sum_{j=1}^{\lfloor{\frac{m}{d}}\rfloor}\sum_{x|gcd(i,j)}\mu(x)\;(d\in prime)\\&= \sum_{d=1}^n\sum_{x=1}^{\lfloor{\frac{n}{d}}\rfloor}\;\mu(x) \lfloor{\frac{n}{dx}}\rfloor\lfloor{\frac{m}{dx}}\rfloor \;(d\in prime) \end{aligned} \]

honorific title\(T=dx\)Then there is:

\[\begin{aligned}Ans&= \sum_{T=1}^n\sum_{d|T} \;\mu(\frac{T}{d})\lfloor{\frac{n}{T}}\rfloor\lfloor{\frac{m}{T}}\rfloor (d\in prime)\\&= \sum_{T=1}^n\;\lfloor{\frac{n}{T}}\rfloor\lfloor{\frac{m}{T}}\rfloor \sum_{d|T} \;\mu(\frac{T}{d})(d\in prime) \end{aligned} \]

discoveries\(g(T)= \sum_{d|T} \mu(\frac{T}{d})\) is something that can be processed out in advance by enumerating the multiples of a prime number, summing the prefixes over it, and then number theory chunking it.

Click to view code
#include<bits/stdc++.h>
using namespace std;
const int Ratio=0;
const int N=1e7+5,M=1e7;
int u[N],pri[N],tot,yz[N],g[N];
void Wpre()
{
    u[1]=1;
    for(int i=2;i<=M;i++)
    {
        if(!yz[i]) pri[++tot]=i,u[i]=-1;
        for(int j=1;j<=tot;j++)
        {
            if(i*pri[j]>M) break;
            yz[i*pri[j]]=1;
            if(i%pri[j]==0) break;
            u[i*pri[j]]=-u[i];
        }
    }
    for(int i=1;i<=tot;i++) for(int j=1;j<=M;j++)
    {
        if(pri[i]*j>M) break;
        g[pri[i]*j]+=u[j];
    }
    for(int i=2;i<=M;i++) g[i]+=g[i-1];
}
int main()
{
    Wpre();
    int T,n,m;scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        if(n>m) swap(n,m);
        long long res=0;
        for(int l=1,r;l<=n;l=r+1)
            r=min(n/(n/l),m/(m/l)),res+=1ll*(g[r]-g[l-1])*(n/l)*(m/l);
        printf("%lld\n",res);
    }
    return Ratio;
}

approximate sum of numbers

Personally, I find it easier, the point is to ask for evidence\(d(i,j)=\sum_{x|i}\sum_{y|j}[gcd(x,y)=1]\)

simple certificate

image

Excerpted from an inscription by Siyuan Luogu.

\[\begin{aligned}Ans&= \sum_{i=1}^n\sum_{j=1}^m\;d(ij)\\&= \sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j}\;[gcd(x,y)=1]\\&=\sum_{i=1}^n\sum_{j=1}^m\sum_{x|i}\sum_{y|j}\sum_{d|gcd(x,y)}\mu(d)\\&=\sum_{i=1}^n\sum_{j=1}^m\;\lfloor{\frac{n}{i}}\rfloor\lfloor{\frac{m}{j}}\rfloor\sum_{d|gcd(i,j)}\mu(d)\\&=\sum_{d=1}^n\sum_{i=1}^{\lfloor{\frac{n}{d}}\rfloor}\sum_{j=1}^{\lfloor{\frac{m}{d}}\rfloor}\lfloor{\frac{n}{id}}\rfloor\lfloor{\frac{m}{jd}}\rfloor\mu(d)\\&=\sum_{d=1}^n\;\mu(d)\sum_{i=1}^{\lfloor{\frac{n}{d}}\rfloor}\sum_{j=1}^{\lfloor{\frac{m}{d}}\rfloor} \lfloor{\frac{n}{id}}\rfloor\lfloor{\frac{m}{jd}}\rfloor\\&=\sum_{d=1}^n\;\mu(d)\,(\sum_{i=1}^{\lfloor{\frac{n}{d}}\rfloor}\,\lfloor{\frac{n}{id}}\rfloor)\,(\sum_{j=1}^{\lfloor{\frac{m}{d}}\rfloor}\,\lfloor{\frac{m}{jd}}\rfloor) \end{aligned} \]

The last two lumps look familiar don't they, and yes it is a template for number theory chunking. The scope of this question is\(n\le 5\times10^5\), which is relatively small, so it's a direct response to the\(\mu(d)\) Take the prefix sum and\(\mathcal{O(n\sqrt{n})}\) preprocessor\(g(n)=\sum_{i=1}^n \lfloor{\frac{n}{i}}\rfloor\) values, and then applying number-theoretic chunking is sufficient, with a query complexity of\(\mathcal{O(T\sqrt{n})}\)

Click to view code
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int Ratio=0;
const int N=5e4+5,M=5e4;
int u[N],pri[N],tot,yz[N],sum[N];
ll g[N];
void Wpre()
{
    u[1]=1;
    for(int i=2;i<=M;i++)
    {
        if(!yz[i]) pri[++tot]=i,u[i]=-1;
        for(int j=1;j<=tot;j++)
        {
            if(i*pri[j]>M) break;
            yz[i*pri[j]]=1;
            if(i%pri[j]==0) break;
            u[i*pri[j]]=-u[i];
        }
    }
    for(int i=1;i<=M;i++) sum[i]=sum[i-1]+u[i];
    for(int i=1;i<=M;i++)
    {
        ll res=0;
        for(int l=1,r;l<=i;l=r+1)
            r=i/(i/l),res+=1ll*(r-l+1)*(i/l);
        g[i]=res;
    }
}
int main()
{
    Wpre();
    int T,n,m;scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        if(n>m) swap(n,m);
        ll res=0;
        for(int l=1,r;l<=n;l=r+1)
            r=min(n/(n/l),m/(m/l)),res+=(sum[r]-sum[l-1])*g[n/l]*g[m/l];
        printf("%lld\n",res);
    }
    return Ratio;
}

stopwatch

They all say it's a board question, but I hit thesurname SanDays.

Along the lines of being able to get the questions down, let's ignore the\(a\) The limitations of the set\(\sigma (x)\) because of\(x\) The factorization of the sum, then there is clearly:

\[\begin{aligned}Ans&=\sum_{i=1}^n\sum_{j=1}^m\;\sigma(gcd(i,j))\\&= \sum_{d=1}^n\sum_{i=1}^n\sum_{j=1}^m \;[gcd(i,j)=d]\;\sigma(d)\\&=\sum_{d=1}^n\sum_{i=1}^{\lfloor{\frac{n}{d}}\rfloor{}}\sum_{j=1}^{\lfloor{\frac{m}{d}}\rfloor{}}\;[gcd(i,j)=1]\;\sigma(d)\\&=\sum_{d=1}^n\sum_{i=1}^{\lfloor{\frac{n}{d}}\rfloor{}}\sum_{j=1}^{\lfloor{\frac{m}{d}}\rfloor{}}\sum_{x|gcd(i,j)}\mu(x)\,\sigma(d)\\&= \sum_{d=1}^n\;\sigma(d)\sum_{x=1}^{\lfloor{\frac{n}{d}}\rfloor{}}\;\mu(x)\lfloor{\frac{n}{dx}}\rfloor{}\lfloor{\frac{m}{dx}}\rfloor{} \end{aligned} \]

honorific title\(T=dx\)Then there is:

\[\begin{aligned}Ans&= \sum_{T=1}^n \sum_{d|T} \;\sigma(d)\,\mu(\frac{T}{d})\,\lfloor{\frac{n}{T}}\rfloor{}\lfloor{\frac{m}{T}}\rfloor{}\\&=\sum_{T=1}^n\;\lfloor{\frac{n}{T}}\rfloor{}\lfloor{\frac{m}{T}}\rfloor{}\sum_{d|T}\;\sigma(d)\,\mu(\frac{T}{d}) \end{aligned} \]

If you don't know how to find the \(\sigma\) function, look here.

At this point in the chemicalization, the latter part can already be processed in advance, at this point consider adding the\(a\) The constraints of the

Let $g(T)=\sum_{d|T} \sigma(d),\mu(\frac{T}{d}) $ when\(\sigma(d)\le a\) will have an impact on\(g(T)\) produces a contribution, and for all multitests, it is only the specification of the rectangle that changes, not the value.

Then we can do it completely offline! Speaking of all inquiries press\(a\) Ascending order, whenever\(a\) When the value of the prefix becomes larger, insert the corresponding value for the place where there is a change. It just so happens that what we need is a prefix and and with fix, so consider a tree array to maintain the\(g(T)\) The prefix sum of the function.

The complexity of inserting values is approximated by the harmonic series, and the complexity of updating the tree array is\(\mathcal{O(\log n)}\)Therefore, the total complexity of the modification is\(\mathcal{O(n\log^2 n)}\); optimize queries using number-theoretic chunking\(\mathcal{O(\sqrt{n})}\), Tree Array Query\(\mathcal{O(\log n)}\)Therefore, the total complexity of the query is\(\mathcal{O(q\sqrt{n}\log n)}\)The program's Total program complexity\(\mathcal{O(n\log^2 n+q\sqrt{n}\log n)}\)

Click to view code
#include<bits/stdc++.h>
#define _(a,b) make_pair(a,b)
#define fi first
#define se second
typedef long long ll;
using namespace std;
const int Ratio=0;
const int N=1e5+5,M=1e5;
int u[N],pri[N],tot,yz[N],low[N];
int ans[N],v[N];
pair<int,int> o[N];
struct rmm{int n,m,a,id;}q[N];
bool cmp(rmm A,rmm B){return <;}
void Wpre()
{
    u[1]=1,o[1]=_(1,1);
    for(int i(2);i<=M;i++)
    {
        if(!yz[i]) pri[++tot]=i,u[i]=-1,low[i]=i+1,o[i]=_(i+1,i);
        for(int j(1);j<=tot;j++)
        {
            if(i*pri[j]>M) break;
            yz[i*pri[j]]=1;
            if(i%pri[j]==0)
            {
                low[i*pri[j]]=low[i]*pri[j]+1;
                o[i*pri[j]]=_(o[i].fi/low[i]*low[i*pri[j]],i*pri[j]);
                break;
            }
            u[i*pri[j]]=-u[i];
            low[i*pri[j]]=pri[j]+1;
            o[i*pri[j]]=_(o[i].fi*o[pri[j]].fi,i*pri[j]);
        }
    }
    sort(o+1,o+M+1);
}
void Wupd(int x,int k){for(;x<=M;x+=(x&-x)) v[x]+=k;}
int Wq(int x)
{
    int res=0;
    while(x) res+=v[x],x-=(x&-x);
    return res;
}
int main()
{
    Wpre();
    int T;scanf("%d",&T);
    for(int i(1);i<=T;i++) scanf("%d%d%d",&q[i].n,&q[i].m,&q[i].a),q[i].id=i;
    sort(q+1,q+1+T,cmp);
    int j=1;
    for(int i(1);i<=T;i++)
    {
        while(j<=M&&o[j].fi<=q[i].a)
        {
            for(int k(o[j].se);k<=M;k+=o[j].se)
                Wupd(k,o[j].fi*u[k/o[j].se]);
            j++;
        }
        int res=0,n=q[i].n,m=q[i].m;
        if(n>m) swap(n,m);
        for(int l(1),r;l<=n;l=r+1)
            r=min(n/(n/l),m/(m/l)),res+=(Wq(r)-Wq(l-1))*(n/l)*(m/l);
        ans[q[i].id]=res;
    }
    for(int i(1);i<=T;i++) printf("%d\n",(ans[i]&(~(1<<31))));
    return Ratio;
}

DZY Loves Math

There is a new function, ignore it for now and push the equation.

\[\begin{aligned}Ans&=\sum_{i=1}^n\sum_{j=1}^m \;f(gcd(i,j))\\ &=\sum_{d=1}^n\sum_{i=1}^n\sum_{j=1}^m\;[gcd(i,j)=d] \,f(d)\\&=\sum_{d=1}^n\sum_{i=1}^{\lfloor{\frac{n}{d}}\rfloor{}}\sum_{j=1}^{\lfloor{\frac{m}{d}}\rfloor{}}\;[gcd(i,j)=1]\,f(d)\\&=\sum_{d=1}^n\;f(d)\sum_{i=1}^{\lfloor{\frac{n}{d}}\rfloor{}}\sum_{j=1}^{\lfloor{\frac{m}{d}}\rfloor{}}\sum_{x|gcd(i,j)}\mu(x)\\&=\sum_{d=1}^n\;f(d)\sum_{x=1}^{\lfloor{\frac{n}{d}}\rfloor{}}\;\mu(x)\lfloor{\frac{n}{dx}}\rfloor{}\lfloor{\frac{m}{dx}}\rfloor{} \end{aligned} \]

honorific title\(T=dx\)Then there is:

\[\begin{aligned}Ans&=\sum_{T=1}^n\;\lfloor{\frac{n}{T}}\rfloor{}\lfloor{\frac{m}{T}}\rfloor{}\sum_{d|T}\;f(d)\,\mu(\frac{T}{d}) \end{aligned} \]

It seems to do the job up to this point, but the latter lump $g(T)=\sum_{d|T}\ f(d)\ \mu(\frac{T}{d}) $ needs to be reconciled with the progression preprocessing, the\(n\le 10^7\), which was able to run on the question bank a month ago, but now it's half as slow for some reason, so we need to continue to optimize and process it out with linear complexity.

We focus on\(g(T)\) This function. Set\(T\) have altogether\(k\) A different prime factor is decomposed into $T=\prod_{i=1}^k\ p_i^{a_i} $ . Let\(T\) A factor of\(d\) decompose as\(d=\prod_{i=1}^k \;p_i^{b_i}\)Discover\(d\) There is a contribution if and only if\(\mu(\frac{T}{d})\neq 0\)namely\(\forall i\in[1,k], \;a_i-b_i\le 1\)In other words.\(b_i\) can only take the value of\(a_i\) maybe\(a_i-1\)

Then there are two more scenarios:

one type of\(a_i\) The case of not all equal, then there must $ exist \ i,j\in\ [1,k],a_i\lt a_j $, consider\(b_i\) regardless of whether one takes\(a_i\) maybe\(a_i-1\)It's not going to be a problem for\(f(T)\) have an effect on the value of and the two ways of taking the\(\mu\) The sum of the values is\(0\), ie:At this point, no matter how it's distributed\(b_i\) values, the final result can always be assigned two-by-two to sum to\(0\) situation, therefore\(g(T)=0\)

in addition\(a_i\) All equal cases. At this point there is a contribution\(d\) have altogether\(2^k\) The values are known to be\(\binom{0}{k}+\binom{2}{k}+\cdots+\binom{2\times \lfloor{\frac{k}{2}}\rfloor{}}{k}=\binom{1}{k}+\binom{3}{k}+\cdots+\binom{2\times \lfloor{\frac{k-1}{2}}\rfloor{}+1}{k}\), i.e., the sum of the odd terms in each row of Yang Hui's triangle is equal to the sum of the even terms. The number above in parentheses corresponds exactly to\(a_i-b_i\) The median value is\(1\) The number of\(f(d)\) All being equal, the\(g(T)\) The value of\(0\). But when the number above the parentheses is equal to\(k\)namely\(\forall \;i\in[1,k],b_i=a_i-1\) when\(f(d)=a_i-1\)

Understand it a little bit and then come back to the situation. If\(k\) is odd, then when\(\forall\;i\in[1,k],b_i=a_i-1\) when\(\mu(\frac{T}{d})=(-1)^k=-1\), i.e., in the step that contributes to the result one should have subtracted the\(a_i\)but actually subtracted\(a_i-1\)Then finally\(g(T)=1\)if\(k\) is an even number congruent to the fact that at this point\(\mu(\frac{T}{d})=1\)Then it would have been better to add\(a_i\)But in reality it only adds\(a_i-1\)Eventually\(g(T)=-1\)

Integrate it and find out\(g\) The function takes the following values:

\[g(T)=\begin{cases}0\quad\quad\quad\quad\quad presence \; i,j\in[1,k],a_i\lt a_j\\\ (-1)^{k+1}\quad\, \forall\;i,j\in[1,k],a_i=a_j \end{cases} \]

included among these\(k\) because of\(T\) The number of prime factors of the

In the implementation, record the exponent of the smallest prime factor and its exponential power, and when transferring, determine whether the exponent of the second smallest prime factor after removing the smallest prime factor is the same as it can be.

preprocessing\(g\) The complexity of the function and the prefix sum is\(\mathcal{O(n)}\), the query complexity after number-theoretic chunking optimization is\(\mathcal{O(T\sqrt{n})}\)Total complexity\(\mathcal{O(n+T\sqrt{n})}\)

Click to view code
#include<bits/stdc++.h>
typedef long long ll;
using namespace std;
const int Ratio=0;
const int N=1e7+5,M=1e7;
int n,m;
int u[N],pri[N],tot,yz[N],Index[N],low[N],g[N];
void Wpre()
{
    u[1]=1,g[1]=0;
    for(int i(2);i<=M;i++)
    {
        if(!yz[i]) low[i]=pri[++tot]=i,u[i]=-1,Index[i]=g[i]=1;
        for(int j(1);j<=tot;j++)
        {
            if(i*pri[j]>M) break;
            yz[i*pri[j]]=1;
            if(i%pri[j]==0)
            {
                Index[i*pri[j]]=Index[i]+1;
                low[i*pri[j]]=low[i]*pri[j];
                if(low[i]==i) g[i*pri[j]]=1;
                else g[i*pri[j]]=Index[i/low[i]]==Index[i*pri[j]]?-g[i/low[i]]:0;
                break;
            }
            u[i*pri[j]]=-u[i];
            Index[i*pri[j]]=1;
            low[i*pri[j]]=pri[j];
            g[i*pri[j]]=Index[i]==1?-g[i]:0;
        }
    }
    for(int i(2);i<=M;i++) g[i]+=g[i-1];
}
int main()
{
    Wpre();
    int T;scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        if(n>m) swap(n,m);
        ll res=0;
        for(int l(1),r;l<=n;l=r+1)
            r=min(n/(n/l),m/(m/l)),res+=1ll*(g[r]-g[l-1])*(n/l)*(m/l);
        printf("%lld\n",res);
    }
    return Ratio;
}

Other examples will be updated gradually.

It's not easy to make, if you help, please recommend support, thanks!