Article From:

Number theory is divided into pieces: it should be considered as a kind of thought

What is a number theory block

My understanding of logarithmic partition is that in a mathematical problem that requires statistics of $\sum_{i}^{n}{f (I) $$, because $f (I) $is monotone, there are $x, y \in [i, j]$.$f(x)=f(y)$。As long as we find this interval, we can save the time cost of every function value in the calculation interval.

The time complexity is largely $O (\sqrt n) $?

The introduction of number theory

【$\sum_{i}^{}{⌊\frac{n}{i}⌋}$】Example 1: the study of bzoj1968: [Ahoi2005]COMMON divisor




There is only one row and one integer N (0 < N < 1000000).


There is only one row output, which is the sum of integer M, that is, f (1) to f (N).

 Topic analysis

The answer is all the number and number of $1..X$.

We know that the answer to $\sum_{i}^{}{is \frac{n}{i} $$.

So the violence algorithm comes: so we

1 for (int i=1; i<=n; i++)
2     ans += n/i;

Just fine.

Because of $n=10^6$, the algorithm of $O (n) is past. But not! This is the problem of number theory. How can we stop at the algorithm of $O (n)?

If $g (I) $is used to represent $\frac{n}{i}$, it is obvious that $ans=\sum_{i=1}^{n}{g (I) is $, and $g (I) is not strictly monotonic.

It is natural to think that we can not find out $[i and j]$when we ask for $g (I) $.

Here is a conclusion that $j=, {\frac{n}{, \frac{n}{i}, and p $are the following to prove this conclusion.

We have $j=, {\frac{n}{, \frac{n}{i}, \frac{n}{i}, \leq, {\frac{n}{, \frac{n}{i},}}&lt, j+1$, and so on.

\begin{cases}⌊\frac{n}{i}⌋\leq \frac{n}{j}\\\frac{n}{j+1}<{⌊\frac{n}{i}⌋}\end{cases}

So $j$is the maximum to satisfy the condition.


 1 #include<bits/stdc++.h>
 2 typedef long long ll;
 4 int n;
 5 ll ans;
 7 int main()
 8 {
 9     register int i,j;
10     scanf("%d",&n);
11     for (i=1; i<=n; i=j+1)
12         j = n/(n/i),
13         ans += 1ll*(j-i+1)*(n/i);
14     printf("%lld\n",ans);
15     return 0;
16 }


【$\sum_{i}^{}{⌊\frac{n}{i}⌋}$Variant] case two:

Title Description

Given two integerslandr

For arbitrarilyx,satisfyl≤x≤r,holdxAll the divisors are written down.

For each written number, only the highest digit number is reserved. seek[1,9]The number of numbers that appear in each of the numbers.

Data range

For 100% data: $1 < l < < R < 10^9$

Topic analysis

The difference here is that each factor keeps only the highest digit number, which means that the answer is added to different places.

Obviously, the answer is subtraction, so we can deal with $[1,9]$in a similar way.

 1 #include<bits/stdc++.h>
 2 typedef long long ll;
 4 int l,r;
 6 ll work(ll x, ll a, ll b)
 7 {
 8     ll ret = 0, j = 0;
 9     for (ll i=a; i<=b; i=j+1)
10         j = std::min(x/(x/i), b),
11         ret += 1ll*(j-i+1)*(x/i);
12     return ret;
13 }
14 ll get(ll x, ll p)
15 {
16     ll ret = 0, t = 1;
17     for (; x>=p; t*=10, p*=10)
18         ret += work(x, p, std::min(x, p+t-1));
19     return ret;
20 }
21 int main()
22 {
23     scanf("%d%d",&l,&r);
24     for (int i=1; i<=9; i++)
25         printf("%lld\n",get(r, i)-get(l-1, i));
26     return 0;
27  }

Here, $get (x, P) $represents the total number of answers in the $1..X$number, where the highest factor is $p$. For example, $p=3$, then the number of $p$with the highest position must be $300..399$, $3000… 3999$.

The $work (x, a, b) $after that indicates that $a..B$is the number of $x$factors. This step is transformed into a model of $\sum_{i}^{}{\frac{n}{i} $$, so it can be divided into blocks by number theory.

At this point, this strange question turned into a common model.


【$\sum_{i}^{}{⌊\frac{n}{i}⌋}$Variant] case three: the sum of the remainder of 1257: [CQOI2007]


Give positive integers n and K, calculate J (n, K) =k mod 1 + K mod 2 + K mod 3 +… The value of + K mod n
The K mod I indicates that the K is divided by the remainder of the I.
For example, J (5, 3) =3 mod 1 + 3 mod 2 + 3 mod 3 + 3 mod 4 + 3 mod 5=0+1+0+3+3=7


The input is only one line, which contains two integers n, K.
1<=n ,k<=10^9


The output is only one line, that is, J (n, K).

Topic analysis

The mod operation here does not increase monotonously. It looks like metaphysics seems to be transformed into other models. But let’s change the formula.

$$=\sum_{i=1}^{n}{(K-i*⌊\frac{K}{i}⌋)}  \\

So we found it back to the basic model again!

 1 #include<bits/stdc++.h>
 2 typedef long long ll;
 4 ll n,k,ans;
 6 int main()
 7 {
 8     register int i,j;
 9     scanf("%lld%lld",&n,&k);
10     ans = n*k;
11     for (i=1; i<=n; i=j+1)
12     {
13         if (!(k/i)) break;
14         j = std::min(k/(k/i), n);
15         ans -= 1ll*(j+i)*(j-i+1)/2*(k/i);
16     }
17     printf("%lld\n",ans);
18     return 0;
19 }






Link of this Article: Elementary number theory block

Leave a Reply

Your email address will not be published. Required fields are marked *