nubir345's blog

Tricks that I learnt while practicing
By nubir345, 4 years ago, In English

This blog is for personal use. You can check it out if you want.

As many people are checking out this blog, I thought of adding problems for some of the tricks.

Tricks

  1. Sum-Xor property: $$$ a+b = a \oplus b + 2(a\And b) $$$. Extended Version with two equations: $$$a+b=a\vert b + a\And b$$$ AND $$$a \oplus b = a\vert b - a\And b$$$ Problem 1 Problem 2
  2. Upto $$$10^{12}$$$ there can be atmost $$$300$$$ non-prime numbers between any two consecutive prime numbers.
  3. Any even number greater than $$$2$$$ can be split into two prime numbers. Problem1 Problem 2
  4. Sometimes it is better to write a brute force / linear search solution because its overall complexity can be less. Problem 1
  5. When $$$A \leq B$$$ then $$$\lfloor \frac{B-1}{A} \rfloor \leq N \leq \lceil \frac{B-1}{A} \rceil$$$ where $$$N$$$ is the number of multiples of A between any two multiples of B. Problem 1
  6. Coordinate Compression Technique when value of numbers doesn't matter. It can be done with the help of mapping shortest number to $$$1$$$, next greater to $$$2$$$ and so on. Problem 1
  7. Event method: When there is a problem in which two kinds of events are there (say $$$start$$$ and $$$end$$$ events), then you can give $$$-ve$$$ values to $$$start$$$ events and $$$+ve$$$ values to $$$end$$$ events, put them in a vector of pairs, sort them and then use as required. Problem 1 Problem 2
  8. When applying binary search on $$$doubles$$$ / $$$floats$$$ just run a loop upto 100 times instead of comparing $$$l$$$ and $$$r$$$. It will make things easier.
  9. For binary search you can also do binary lifting sort of thing, see this for more details. (I don't know how to add that code without messing up the list, that's why the link). Problem 1 Problem 2
  10. Sometimes, it is useful to visualize array into a number of blocks to move towards a solution.
  11. $$$gcd(F_n,F_m)=F_{gcd(n,m)}$$$, where $$$F_x$$$ is the $$$x_{th}$$$ fibonacci numbers and first two terms are $$$0,1$$$. Problem 1
  12. In ternary search, always keep in mind that when $$$r=l+2$$$ then $$$mid1=l$$$ and $$$mid2=r$$$ or we can say that $$$l$$$ & $$$r$$$ will remain same $$$i.e.$$$ $$$r=l+2$$$ and the condition $$$l+1$$$ will never get checked, so you have to check it explicitly. see this problem

Also, if you know any tricks / methods that you want to share and are not in the blog then you can write in the comment section, I will add them to the blog.
I will update this blog if I come across any more general methods / tricks.

  • Vote: I like it
  • +472
  • Vote: I do not like it

Comments Comments (124)
| Write comment?
»
4 years ago, # |
  Vote: I like it +319 Vote: I do not like it

If you know the proof of #3, please tell me.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    I don't know the proof. It is not proved yet. But it is also not proved wrong (I think).

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it -12 Vote: I do not like it

    I used google and got this: https://arxiv.org/pdf/1811.02415.pdf and https://vixra.org/pdf/1702.0150v1.pdf

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +37 Vote: I do not like it

      By the way, it's a fine exercise. Find mistakes in the second one (the first one is significantly longer).

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +36 Vote: I do not like it

        After 11 paragraphs of the second "proof", we just reached this impressive conclusion:

        "Therefore, we only need to prove that 2k, for every integer k > 1,is the sum of two primes."

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yup, that was the funniest part IMO.

          → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Those papers are from arxiv.. they are not peer reviewed papers..the proofs in those articles have either been proven to be false or else no has bothered to verify it being patently flawed.

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +2 Vote: I do not like it

      The proof called the goldbach conjecture. Many of mathematics are working hard to prove it. As a competitive programmer. The prove is simple green text "Accept".

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it -6 Vote: I do not like it

    There is no proof , only Goldbach Conjecture

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +133 Vote: I do not like it

    I have discovered a truly marvelous proof of this, which this webpage is too narrow to contain.

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Why will I tell you if I can win one million dollars? :v Anyway you can use it in this problem.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +116 Vote: I do not like it

    The proof is the green text that says "Accepted".

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -29 Vote: I do not like it

      Depends on how strong are the system tests.

      → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it +52 Vote: I do not like it

    FWIW it's definitely been verified for numbers below $$$10^{18}$$$, so it's completely fine to use that property for any long longs (which is basically always the case for us).

    On this topic, there are some other similar conjectures. ARC 080 D makes use of some more "Goldbach-like" hypotheses.

    → Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 3   Vote: I like it -31 Vote: I do not like it

    We know that any prime number except 2 and 3 can be represented as 6*n+1 or 6*n-1.
    So, Just add two prime numbers:

    1. (6*a+1) + (6*b+1) = (6*a+6*b) +2 //even number
    2. (6*a+1) + (6*b-1) = 6*a+6*b //even number
    3. (6*a-1) + (6*b-1) = (6*a+6*b) -2 //even number

    Let me know if I am wrong.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Trick 7 is my personal favourite

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

nice

→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +15 Vote: I do not like it

This trick is quite well known probably but still maybe it is useful for beginners:
Ways of initializing a global array :

memset(a,0,sizeof(a)) ; // initialize with 0
memset(a,-1,sizeof(a)); // initializing with -1
memset(a,0xc0,sizeof(a)); // initializing with negative infinity
memset(a,0x3f,sizeof(a)); // initializing with positive infinity

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I didn't know about the negative infinity and positive infinity, I guess I will put it in the blog.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      but be careful, if you have something like
      const int INF = [something];
      then INF = 0x3f3f3f3f, not INF = 1e9
      I prefer std::fill(), because you can just fill the array using any arbitrary values that you want, despite being slower

      → Reply
»
4 years ago, # |
  Vote: I like it +33 Vote: I do not like it

For $$$7$$$, you can also do this: for start values, store $$$2*start$$$, and for end values, store $$$2*end+1$$$. If it's even, it will be a start value, else an end value. And start values will always come before end values.

→ Reply
»
4 years ago, # |
  Vote: I like it +12 Vote: I do not like it

I think 6 is coordinate compression

→ Reply
»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

It would be great if everybody could share a few of the peculiar tricks they know

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can you provide links of some problems related to every tricks. It will be very helpful.

→ Reply
»
4 years ago, # |
  Vote: I like it +4 Vote: I do not like it

For trick 1, you can use it on this problem.

A different trick is that for queries, you can sometimes split it into 2 types of queries (when query is greater than sqrt(n) and less than sqrt(n)) so instead of using O(n) time you use O(sqrt(n)). You can use it in these problems 1 2.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    how do we solve this problem? I saw few submissions of this problem, there was dp involved. Can you explain?

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Be careful using unordered_map , it can give TLE or your solution may get hacked , see the blogpost by neal about this link also unordered_map doesn't let you use complex data type like pair<int,int>,int . to make it work see the blog by arpa about it link

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    With custom hash, you can configure it so that it allows

    unordered_map<pair<int, int>, int> mp;
    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Time to add the blog to favorite and read it after eternity.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Any problems related to 7?

→ Reply
»
4 years ago, # |
  Vote: I like it +10 Vote: I do not like it

Can we make this blog like every coder shares their one trick which is not mentioned in the post. It will be a great learning experience for all of us

→ Reply
»
4 years ago, # |
  Vote: I like it -33 Vote: I do not like it

LOL stop treating cp as a game of remembering tricks...

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For trick #8, I usually loop up to 200 times just to be safe. :P

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I heard this somewhere that, if we wanted to find your name in the sorted list of names of people around the globe, it would take no more than 64 operations/iterations for binary search to figure it out. I think that 100 times is more than safe unless the epislon is really small like -1e18 or smth.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it -8 Vote: I do not like it

      That statistic is probably right because $$$2^{64} > 7 \texttt{ billion}$$$. I think that binary search would take at most $$$33 - 34$$$ iterations because $$$log_2{7000000000} \sim 33$$$

      → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can You suggest a problem for the same?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      In CF EDU binary search section, there is a lot of problems about binary search on real values.

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

can you explain 5 one, i mean what is the operator being used?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Do you mean floor and ceil operator? or anything else?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Hey,when i open my profile it is showing that this page is temporarily blocked by the administrator,do you know anything related to it.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Yeah, there were some problems in rating changes in the latest contest. That's why.

        → Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Oh, man!! Point-8 is the best I was getting TLE for some weird reason but this trick got me accepted.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +2 Vote: I do not like it

    With doubles, you should do while(abs(l - r) > EPS) instead of while (l < r).

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      How small should you set EPS?

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      This approach also works but I think you should go with 100 iterations it's just safe.

      → Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Hey bro @nubir345 can u please give the question according to the trick just below each trick , would be very easy for others , the questions given below in comments .

→ Reply
»
4 years ago, # |
  Vote: I like it +16 Vote: I do not like it

When I started with CP, I struggled with Binary search a lot. Nowadays I use these rules-of-thumb for BS.
Say we are doing BS on some variable x. And There is some function bool check(int x) which is monotonic.
And check returns $$$[False, False, ..., False, True, ..., True]$$$ for different values of x and 0 <= x <= 1e9

Code
→ Reply
»
4 years ago, # |
← Rev. 2   Vote: I like it +48 Vote: I do not like it

Also, if you know any tricks / methods that you want to share and are not in the blog then you can write in the comment section, I will add them to the blog.

I'm sure there have been tutorials etc about this trick but since people are talking about binary search, I want to add this. I like to use iterative binary search that looks like this:

int ans = 0;
for (int k = 1 << MAX_LG; k != 0; k /= 2) {
  if (!has_some_property(ans + k)) {
    ans += k;
  }
}

This assumes 0 doesn't have "some property". In the end, ans will be the largest integer that doesn't have "some property".

Using this, I have been able to avoid guessing about one-off errors for 6 years already. It is short to write, intuitive and generalizes well to floats and bigints. I'm not sure exactly what your "trick 8" accomplishes, but I suspect iterative binary search also makes that unnecessary.

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Isn't this Binary Lifting?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I've only ever heard the term "binary lifting" used on trees (problems like "find the $$$k$$$-th ancestor" or LCA). But yes, both of those are essentially binary search.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it +31 Vote: I do not like it

        I don't agree with this. You can do binary jumps instead of binary search but I wouldn't call them the same thing.

        → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    how does this works in case of floats?

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    hi, could you explain how we can use this binary search solve a problem like, "What is the smallest number whose square is strictly larger that a given number N?" Thanks.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Find the largest one that isn't and add 1.

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Since you have been using this for 6 years, have you never run into a binary search problem(not insanely hard) where doing some sort of easy trick(like the +1 thing here) is not applicable? I'm asking because I really like this approach but am kinda scared that if the question is complex enough, i will simply not be able to find the trick so that i can apply this method(obviously in those scenarios going back to the original implementation is always an option).

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          Obviously all kinds of things can happen in insanely hard problems. But no, this can (almost?) always be used in place of binary search. The way I see it, there are 4 use cases for binary search:

          • find the largest number with property $$$P$$$;
          • find the smallest number with property $$$P$$$;
          • find the largest number without property $$$P$$$;
          • find the smallest number without property $$$P$$$

          and all of these can be handled by this implementation.

          → Reply
»
4 years ago, # |
  Vote: I like it +41 Vote: I do not like it

How to get the inversion of just one number?

long long get_inv(long long x)
{
	if (x <= 1) return 1;
	return (p - p / x) * get_inv(p % x) % p;
}
→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    By having memorization, it can be linear $$$O(n)$$$ to get all inversion in $$$[1 \dots n]$$$ (with high constant for modulo ofcourse)

    But if just need to find inversion of one number without using power function, what will be the complexity of the code ?

    I testest for one thousand random integer number (approximately $$$10^9$$$) and I think it is about $$$O(2 * log(n))$$$ am I correct ?

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    What is the difference between your method and the one people usually use (using binary exponentiation)?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Faster and easier (maybe :) ).

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I found this on cp-algorithms. Apparently, it can only be used if x is less than p.

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it +3 Vote: I do not like it

          inv(x) = inv(x % p)

          → Reply
          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Thanks for clarifying, I've just known about that. By the way, there is a slight difference between your code and cp-algorithms' code, your code computes the p - p / x first, before multiplying the result with get_inv(p % x); while cp-algorithms' code computes p / x * get_inv(p % x) % p first, then subtracting the result from p. How can both of them produce the same result?

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              4 years ago, # ^ |
              ← Rev. 2   Vote: I like it +16 Vote: I do not like it

              (p - a) * b % p = (p * b - a * b) % p = (-a * b) % p = p - a * b % p

              → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +3 Vote: I do not like it

      If you add memorization to that function, in theory to say the complexity by this way will be Linear (with high constant for taking modulo), while using binary exponentiation is $$$O(n log n)$$$ (with lighter constant)

      → Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

For trick 1, you can add this great problem.

→ Reply
»
4 years ago, # |
  Vote: I like it +24 Vote: I do not like it

Given a strictly increasing array $$$a_1 < a_2 < a_3 < .... < a_n$$$
Do this transformation $$$a_i := a_i - i$$$
Then the array becomes non- decreasing $$$a_1 <= a_2 <= a_3 <= .... <= a_n$$$
Fairly simple trick but quite useful sometimes :)

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you give link to any problem that use this trick?

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    perhaps i didn't understood this ,but is this applicable to every strictly increasing array? can you show some examples.

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      $$$1, 2, 3, 5, 7$$$ becomes $$$0, 0, 0, 1, 2$$$

      → Reply
      • »
        »
        »
        »
        4 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        what about 2 5 9 23 ?

        → Reply
        • »
          »
          »
          »
          »
          4 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Strictly increasing is a subset of non-decreasing.

          → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      cause if a<b then a<=b-1 and so a-i<=b-(i+1)

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Guys I'm not getting the point 8. Can anyone help me with that?

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    Sometimes precision errors lead to weird behaviour in the while (left <= right) loop in binary search.

    → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

please keep updating this blog it is very helpful

→ Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

for $$$2$$$ and $$$3$$$, every number up to $$${10}^{12}$$$ accepts a goldbach decomposition with one of the numbers less than or equal to $$${10}^6$$$ (I'm not sure if the upper limit is $$${10}^5$$$).

→ Reply
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Problems for 9)
1354D - Multiset
1404C - Fixed Point Removal

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

The second problem in #3 is not related to the Goldbach conjecture.

They use that every even positive integer is a difference of two primes.

If you have any implication between these two conjectures, it would be a big breakthrough in number theory. See e.g. this paper.

→ Reply
»
4 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can anyone help me with problem 1 of point 1 — Xor sum on Atcoder. I failed to solve it but could not find any English editorial for the problem. I found a recursive formula online

$$$f(n) = f(n/2)+f((n-1)/2) + f((n-2)/2) $$$

However, the explanation is in Chinese and GG translate only makes things messier.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +4 Vote: I do not like it

    For each u,v<=n,a xor b=u,a+b=v,consider that if a,b are both even number,then a xor b=u/2,a/2+b/2=v/2,and u/2,v/2<=n/2,so there is f(n/2).

    If a is even and b is odd(or b is even and a is odd),then a/2 xor (b-1)/2=(u-1)/2,a/2+(b-1)/2=(v-1)/2,so there is f((n-1)/2).

    For the same reason,if a,b are both odd,then (a-1)/2 xor (b-1)/2=u/2,(a-1)/2+(b-1)/2=(v-2)/2,u/2<=(v-2)/2(because the reason of xor is always no more than sum)<=(n-2)/2,so there is f((n-2)/2).

    That's why f(n)=f(n/2)+f((n-1)/2)+f((n-2)/2).

    (It's fun that i'm also chinese and i hate messy GG translate too.However,i have to use GG translate to write this explanation lol)

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      And we can also prove these 3 cases are mutually exclusive(i mean that,each u,v is exactly in one case):

      For each u,v(easy to see they are both even or both odd),if u,v are both odd,then it's in case2(an odd and an even in a,b).And for the case u,v are both even,if (v-u)/2 is even,means that a+b dont produce a carry on the last bit,then it's in case1(a,b are both even).For the same reason,if (v-u)/2 is odd,means that a+b produce a carry on the last bit,it's in case3(a,b are both odd).

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thanks a lot.

      → Reply
»
4 years ago, # |
  Vote: I like it +13 Vote: I do not like it 
lcm(a, gcd(b, c)) = gcd(lcm(a, b), lcm(a, c)) -- (1)
gcd(a, lcm(b, c)) = lcm(gcd(a, b), gcd(a, c)) -- (2)

https://mirror.codeforces.com/contest/1350/problem/C

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Wow, this blog is quite useful for me. Upvoted :)

→ Reply
»
4 years ago, # |
  Vote: I like it +17 Vote: I do not like it

$$$F[gcd(x,y)]=gcd(F[x],F[y])$$$

$$$F$$$ is the Fibonacci sequence that $$$F(0)=0$$$, $$$F(1)=1$$$, $$$F(n)=F(n-1)+F(n-2)$$$ for $$$n \ge 2 $$$

→ Reply
»
4 years ago, # |
← Rev. 5   Vote: I like it +1 Vote: I do not like it

You can also add one more property.

gcd ( x , y ) = gcd ( x-y , y );

This results in, gcd ( x , y , z , w ,.....) = gcd ( x-y , y , z , w,....)

Also,

for any a, b, if b > a, a%b = a. Additionally, if a ≥ b > [a/2] , a%b = a - b.

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

For Trick # 2 you can add this Problem

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Using point 2 can we state that for checking if n is prime we just need to check if n is not divisible by any number from 2 to 300 rather than sqrt(n) if n<=1e12?

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    Ofc not: any product of primes greater then 300 not prime but still not divisible by any number from 2 to 300.

    → Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    It just means that when you have to find greatest prime less than 10^12 than you just have to check for 300 numbers (10^12 — 300 to 10^12) if they are prime or not. Max Number of operations would be 300*10^6.

    → Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Here I got one trick , If n>1, then there is always at least one odd prime number x satisfying n < x < 2n

You can check this problem 1178D - Prime Graph

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This has been very helpful, thank you so much!

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Another recent problem that can be solved using trick 1: 1556D - Take a Guess

→ Reply