kazama460's blog

By kazama460, 7 months ago, In English

Hello codeforces community

course updated : 28 October 2020

I have working on Number Theory course which is beginner/Intermediate friendly.The course emphasizes on learning by doing methodology.
After teaching an algorithm/technique and showing how it is implemented we take example practice problems from judges like Codeforces , Codechef , Spoj etc and teach how this algorithm is used in different scenario and how it can be used to solve the problem.
Here is the list of lecture from the course (I will be uploading more lectures soon)

Number Theory Lectures

Any suggestion or criticism is welcome.
Thank you for your valuable time.

PS : Ignore any grammatical mistake as we ignore compiler warnings (My English is not very good)
 
 
 
 
  • Vote: I like it
  • +114
  • Vote: I do not like it

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thanks a ton! I was being looking for that...are there any more topics left?

  • »
    »
    6 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    yes there are many topics I will add , like Chinese remainder theorem

»
6 months ago, # |
  Vote: I like it +2 Vote: I do not like it

Please add the Chinese remainder theorem too. Really appreciate your work!!

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I have watched graph theory course of yours. It's wonderful. Thanks buddy!!

»
6 months ago, # |
  Vote: I like it 0 Vote: I do not like it

WOW!!! UPVOTED. I was looking for this. Many many thanks from me.

»
6 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Chinese remiander theorm

3.A) Derivation of number a which satisfies given crt properties. Suppose we have set of numbers relatively prime with each other eg 3 4 5 and there is a number a: a mod 3 = 2 mod 3 a mod 4 = 2 mod 4 a mod 5 = 1 mod 5

3       4       5

a = 4*5 3*5 3*4

4*5 and 3, 3*5 and 4, 3*4 and 5 are co-prime with each other

Recalling 2 Algorithms: 1) fermats little theorm for inverrse modulo,a and p are co-prime and p is also a prime a^(p-1) == 1 mod p : taking 1/p both sides => a^(p-2) == 1/a mod p which means a^(p-2)%p is the inverse of a wrtx m

2) Extended euclidean algo

now 4*5%3 = 2 hence as the given condition (a mod 3 = 2 mod 3) also satisfies , now action is to be taken now 3*5%4 = 3 hence , as the given condition says it has to be (a mod 4 = 2 mod 4), we first find the modulo inverse of 3*5%4 wrtx 4 i.e invserse of 3 wrtx mod 4, as 3 and 4 are co prime , but 4 is not a prime , hence using extended euclidean algo , we get 3 as modular inverse of 3 wrtx 4. hence 3*5 is multiplied by 3 firstly and then by 2 such that 3*5 * (3 which is mod inverse) *2 ==2 mod 4 now 3*4 mod 5 = 2 mod 5 , using fermat theorm , we get 2^(3)%5 = 3 as mod inverse of 2 wrtx 5, hence multiply 3*4 by 3 for == 1 mod 5

hence the final answer is 3 4 5 a = 4*5 3*5*3*2 3*4*3

hence a is 4*5 + 3*5*3*2 + 3*4*3 = 146 or 146+n*(3*4*5) = 146+n*60

»
5 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

Thank u bro, I took your graph course..That was really nice.