Hi, everyone, we chose the J for the games Div2 in the Bubble Cup competition. Don’t ask me what the Bubble Cup is, I don’t know. It’s just an algorithm contest. Maybe it is because of the low popularity of this competition and the number of participants is not very large, so we chose question J with a medium number of participants as today’s topic.
Link: codeforces.com/contest/142…
This problem is very good, is a high quality math problem, also very much in line with my appetite. Because there are not too many tricks, there is only the collision of thinking and logic.
The question
We all know that for two numbers a and b, we can easily find their greatest common divisor GCD (a,b)\ GCD (a,b) GCD (a,b). We assume that the greatest common divisor of a and B is k. If the lengths of k,ak, BKK, \frac{a}{k}, \frac{b}{k},k,ka, KB form a legitimate triangle, then we assume that a and B are friendly to each other.
For a legitimate triangle, let’s say that its sides are a,b, and c, it has to have a + b > c, a + C > b, and b + C > a, which means that the sum of any two sides is greater than the third side. This should be the content of primary school mathematics teaching, we should be very familiar with.
If a number in a set cannot find a friendly number, it is considered lonely. Now we are given a set of n, representing the set of natural numbers 1-n, and we want to find the number of lonely numbers in the set.
The sample
First, a t (1≤t≤1061\leq t \leq 10^61≤t≤106) is given to represent the amount of test data.
Then a row of T integers representing different n (1≤n≤1061\leq n \le 10^61≤n≤106) is given. For each n, print an integer representing the number of lonely numbers in the set of natural numbers 1-n.
When n=5, the loneliness numbers are 1, 3 and 5 respectively. When n=10, the numbers of loneliness are 1, 5 and 7 respectively.
Answer key
Since the range of n is 1e6, it is impossible to accept the algorithm O(n2)O(n^2)O(n2), so we cannot enumerate all combinations of two numbers. So the brute force solution doesn’t work, we have to analyze the problem and come to other conclusions to simplify the problem.
First of all, it’s easy to see that 1 must be lonely. The reason is simple, for any natural number x, its greatest common divisor with 1 is 1. So the result is 1, 1 and x. Since x cannot be repeated with 1, x must be at least 2, but even 2 does not satisfy 1+1>2, so it cannot form a triangle. So no matter what n is, 1 must be lonely.
The other easy point to think about is the case where a and B are mutually prime, which means that their greatest common divisor is 1. So the three sides of the triangle we get are 1, A and b. Similarly, a and B are not equal, so a and B differ by at least 1, so they cannot form the sides of a triangle. So if two numbers are mutually exclusive, then they are definitely not friendly. From this point of view, 1 is lonely precisely because it is interchangeable with all other numbers.
What can we think of from this point?
By the way, you can think of prime numbers. The greatest common divisor of a prime number and all other natural numbers is either 1 or itself. We’ve already done the case where the greatest common divisor is 1, so let’s do the case where the greatest common divisor is itself. Let’s say that this prime number is x and the other number is b, and since the greatest common divisor between x and B is x, that means that B is a multiple of x. So let’s represent b as kx.
So the three sides of the triangle are x, 1, and k. We can get three constraints:
The third one is obvious, and we can ignore it. Let’s take a closer look at the first two. If k+1>x>k−1k +1>x>k−1k +1>x>k−1, x=kx =k. So is there a limit on k? K is also limited, k can not be arbitrarily evaluated, we need to ensure that kx≤ NKX \leq NKX ≤n, which is x≤ NXX \le \frac{n}{x}x≤xn, that is, x≤nx \leq \ SQRT {n}x≤n.
From this line of analysis we arrive at the conclusion that for a prime number x, it must satisfy x≤nx \leq \ SQRT {n}x≤n if it is not alone. If x>nx > \ SQRT {n}x>n, and x is prime, x must be lonely.
Now that we’re done with prime numbers, but we don’t know about composite numbers, are there some composite numbers that are also lonely? Well, no, we can prove it this way. Let’s assume that some composite number m that we’re talking about, since it’s composite, must be able to factor prime factors. And it must be able to factor out a prime factor less than n\ SQRT {n}n, which is easy to prove because composite numbers are either square numbers or have at least two prime factors. In either case, as long as its prime factor is greater than or equal to n\ SQRT {n}n, it must be greater than n. So this is a contradiction.
Since composite numbers must find a prime factor less than n\ SQRT {n}n, we can assume that the prime factor is x and write the composite number m as ax. The range of a should be [2,nx][2, \frac{n}{x}][2,xn]. So what we need to do is to find a number b such that bx is friendly to Ax, and bx≤ NBX \le NBX ≤n, and a and B are mutually essential, otherwise we cannot satisfy GCD (ax,bx)=x\ GCD (ax,bx)= XGCD (ax,bx)=x.
So can we find b like this? Of course it can, and it’s very, very simple. Let’s first analyze the conditions we need to achieve, since there are four conditions we need to achieve in order to make the triangle legal:
From the first two conditions, we can obtain the range of B a−x
XA > XA >x, then we can choose b is equal to a minus 1, so b must satisfy this condition. If a is less than x, we can choose b is equal to x. Since x is prime and a is less than x, we can guarantee that a and x are mutually prime.
In this way, we have proved that all composite numbers must not be lonely, and they can all find their own friendly numbers.
So, ultimately, what we want is the number of primes greater than n\ SQRT {n}n, but don’t forget to add 1, because 1 is also a lonely number that satisfies this condition. Since n is at most 10610^6106, it would be too late to solve for primes one by one, so here we can use the Escrow sieve that we introduced earlier to solve for all primes very quickly.
The other question is, what do we do with the number of primes in a certain range? It’s really easy, we just use the prefix and.
In addition to these, there is another problem with this problem is that the time is very tight. As a result, the Python implementation of the same algorithm would time out, so I had no choice but to use the ancestral C++ to rewrite it again, and finally passed. If you look at the efficiency gap between Python and C++, it’s pretty impressive.
Finally, attach the code:
#include <iostream>
#include <cstdio>
#include <cstring>
#include <queue>
#include <vector>
#include <cmath>
#include <cstdlib>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include "time.h"
#include <functional>
// Some macro definitions
#definerep(i,a,b) for (int i=a; i<b; i++)
#defineRep(i,a,b) for (int i=a; i>=b; i--)
#defineforeach(e,x) for (__typeof(x.begin()) e=x.begin(); e! =x.end(); e++)
#define mid ((l+r)>>1)
#define lson (k<<1)
#define rson (k<<1|1)
#define MEM(a,x) memset(a,x,sizeof a)
#define L ch[r][0]
#define R ch[r][1]
using namespace std;
const int N=1000050;
const long long Mod=1000000007;
int t, query[N];
int isprime[N], primecnt[N];
// Sieve method
void eratosthenes(a) {
rep(i, 0, N) isprime[i] = 1;
rep(i, 2, N) {
if (isprime[i]) {
for (int j = i+i; j < N; j += i) {
isprime[j] = 0; }}}// Maintain prefixes and primes
rep(i, 2, N) {
primecnt[i] = primecnt[i- 1] + isprime[i]; }}int main(a) {
eratosthenes(a);scanf("%d", &t);
rep(i, 0, t) {
int query;
scanf("%d", &query);
printf("%d\n", primecnt[query] - primecnt[int(sqrt(query))] + 1);
}
return 0;
}
Copy the codeThat’s all for today’s article. I sincerely wish you all a fruitful day. If you still like today’s content, please join us in a three-way support.
Original link, ask a concern