Number theoretic function and its summation to be updated

Mainly record the relevant topics , Skip knowledge explanation .

Example 1 Number theory is divided into blocks

P3935 Calculating

Title Description

if $x$ The result of decomposing the prime factor is $x=p_1^{k_1}{p}_2^{k_2}\cdots p_n^{k_n}$, Make $f(x)=(k_1+1)(k_2+1)\cdots (k_n+1)$, seek ${\sum }_{i=l}^{r}f(i)$ Yes $998244353$ Results of die taking .
Time complexity $O(\sqrt{n})$.

Ideas

The first thing to know is $f(x)$ In fact, that is $x$ The approximate number of .（ Every prime factor has $k_i$ Then you can take $0,1,...,k_i$ altogether $k_i+1$ Sort and combine , From the unique decomposition theorem, it is obvious that the products are different ） Because the topic requires interval and , Then it is normally transformed into prefix and form $ans={\sum }_{i=1}^{r}f(x)-{\sum }_{i=1}^{l-1}f(x)$ , set up $S(n)={\sum }_{i=1}^{n}f(x)$, The problem is transformed into seeking $S(n)$ , That is to say seek $1-n$ this $n$ The sum of the number of factors .

$1-n$ There are factors $i$ There are a total of $\lfloor \frac{n}{i}\rfloor$ , Directly use number theory to divide into blocks .

Code

int ll, rr, n;
int cal(int l, int r) {
    
	int ansr = 0, ansl = 0;
	n = rr;
    for(int l=1,r;l<=n;l=r+1){
    
        r=n/(n/l);
        ansr+=(n/l)*(r-l+1) % P;	
        ansr %= P;
    }
    n = ll;
    for(int l=1,r;l<=n;l=r+1){
    
        r=n/(n/l);
        ansl+=(n/l)*(r-l+1) % P;	
        ansl %= P;
    }
    ansr = (ansr - ansl + P) % P;
    return ansr;
}
void solve() {
    
    cin >> ll >> rr;
    ll--;
    cout << cal(ll, rr) << endl;
}

Example 2 Number theory is divided into blocks

P2303 [SDOI2012] Longge The problem of

Title Description

Given an integer $n$, You need to figure out $\sum _{i=1}^n\gcd (i,n)$,$n<10^9$

Ideas

be aware $gcd(i,n)$ The maximum value of is $n$ The approximate number of , So consider classification by value , And it appears $gcd$ Problems often need to find a way to figure out $gcd(i,j)=1$, So we change the original formula into $$\sum _{d|n}d\sum _{i=1}^n[gcd(i,n)=d]=\sum _{d|n}d\sum _{i=1}^{\frac{n}{d}}[gcd(i,\frac{n}{d})=1]=\sum _{d|n}d\varphi (\frac{n}{d})$$
You can enumerate $n$ Directly find the divisor of , Time complexity $O(\sqrt{n})$.

Code

void solve() {
    
    cin >> n;
    ll ans = 0;
    for(ll i = 1; i * i <= n; i++) {
    
    	if(n % i == 0) {
    
	    	ans += i * phi(n/i);
	    	if(n/i!=i) {
    
	    		ans += (n/i) * phi(i);
	    	}
    	}
    }
    cout << ans << endl;
}

Mobius function

Convolution is often used

$ϵ=\mu \ast 1,Id=\varphi \ast 1$ .
namely $ϵ(n)={\sum }_{d|n}\mu (d)$ . among $ϵ(n)=1$ If and only if $n=1$, otherwise $=0$ .

Cited example

Given $n,m$, Find two tuples $(x,y)$ The number of , Satisfy $1\le x\le n$ , $1\le y\le m$ , And $gcd(x,y)=1$ .$n,m\le 10^7$ , at most $10^4$ Group data .

Ideas

$$\sum _{x=1}^n\sum _{y=1}^m[gcd(x,y)=1]=\sum _{x=1}^n\sum _{y=1}^mϵ(gcd(x,y))=\sum _{x=1}^n\sum _{y=1}^m\sum _{d|gcd(x,y)}\mu (d)$$
$$=\sum _{x=1}^n\sum _{y=1}^m\sum _{d|x,d|y}\mu (d)==\sum _{d=1}^{min(n,m)}\mu (d)\lfloor \frac{n}{d}\rfloor \lfloor \frac{m}{d}\rfloor$$
Pretreatment of the above formula $\mu$ And its prefix and , Press $\lfloor \frac{n}{d}\rfloor \lfloor \frac{m}{d}\rfloor$ The value segment of , You can ask each group $O(\sqrt{n})$ solve the problem .

Example 3 Mobius inversion

[SDOI2015] About a number and

Title Description

set up $d(x)$ by $x$ The approximate number of , Given $n,m$, seek
$$\sum _{i=1}^n\sum _{j=1}^{m}d(ij)$$
【 Data range 】
about $100\%$ The data of ,$1\le T,n,m\le 50000$.

Ideas

First, there are conclusions ：
$$d(ij)=\sum _{x|i}\sum _{y|j}[gcd(x,y)=1]$$

Then the original formula ：
$$\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 _{x=1}^n\sum _{y=1}^m[gcd(x,y)=1]\lfloor \frac{n}{x}\rfloor \lfloor \frac{m}{y}\rfloor$$
Bring the conclusion of the cited example into ：
$$=\sum _{d=1}^{min(n,m)}\mu (d)\sum _{x=1}^{\lfloor \frac{n}{d}\rfloor }\sum _{y=1}^{\lfloor \frac{m}{d}\rfloor }\lfloor \frac{n}{xd}\rfloor \lfloor \frac{m}{yd}\rfloor =\sum _{d=1}^{min(n,m)}\mu (d)\sum _{x=1}^{\lfloor \frac{n}{d}\rfloor }\sum _{y=1}^{\lfloor \frac{m}{d}\rfloor }\lfloor \frac{\lfloor \frac{n}{d}\rfloor }{x}\rfloor \lfloor \frac{\lfloor \frac{m}{d}\rfloor }{y}\rfloor$$
Make $f(n)={\sum }_{i=1}^n\lfloor \frac{n}{i}\rfloor$ , be
$$=\sum _{d=1}^{min(n,m)}\mu (d)f(\lfloor \frac{n}{d}\rfloor )f(\lfloor \frac{m}{d}\rfloor )$$
also $f(n)={\sum }_{i=1}^n\lfloor \frac{n}{i}\rfloor ={\sum }_{k=1}^{n}d(k)$
Therefore, it can pass the Euler sieve $O(n)$ Preprocessing $d(n)$, By prefix and, we get $f(n)$, You can ask every time $O(\sqrt{n})$ answer .

Code

int mu[maxn], prim[maxn], sum[maxn], cnt;
int g[maxn];
bool vis[maxn];
void get_mu(int n)
{
    
    mu[1]=1;
    for(int i=2;i<=n;i++)
    {
    
        if(!vis[i]){
    prim[++cnt]=i;mu[i]=-1;}
        for(int j=1;j<=cnt&&prim[j]*i<=n;j++)
        {
    
            vis[prim[j]*i]=1;
            if(i%prim[j]==0)break;
            else mu[i*prim[j]]=-mu[i];
        }
    }
    for(int i=1;i<=n;i++)sum[i]=sum[i-1]+mu[i];
    for(int i=1;i<=n;i++)
    {
    
        long long ans=0;
        for(int l=1,r;l<=i;l=r+1)
        {
    
            r=(i/(i/l));
            ans+=1ll*(r-l+1)*1ll*(i/l);
        }
        g[i]=ans;
    }
}
void solve() {
    
    int n, m;
    cin >> n >> m;
    int ans = 0;
    int mn = min(n, m);
    for(int l = 1, r; l <= mn; l = r + 1){
    
    	r = min(n/(n/l), m/(m/l));
        ans += (sum[r] - sum[l-1]) * g[n/l] * g[m/l];
    }
    cout << ans << endl;
}