shakil.ahamed's blog

Number theory practice problems.
By shakil.ahamed, history, 8 years ago, In English

Nothing is well understood unless we can apply it to solve some problems. Currently, I am learning number theory and there is no good classified list of problems for number theory. So, It is difficult to find some problem based on a specific topic.

Here I will maintain a list of problems of number theory in a few category. So, In near future, nobody have to face the same problem. Contribute interesting problems, people(mostly me :D ) will be grateful to you.

1. Divisibility/Primes/Co-prime/GCD/LCM
Problems:
1. LOJ: 1014, 1035
2. CF: 230B, 711E, 585E, 585C, 222C, 546D, GYM101212B
3. SPOJ: LCMSUMH
4. E-OLYMP: 1146, 1243, 1147, 1229, 1244, 1230

2. Continued Fraction
Problems:
1. UVA: 834
2. HackerRank: euler064

3. Diophantine Equations
Problems:
1. LOJ: 1077
2. CF: 7C

4. Functions: Counting Divisors/Divisor Sum
Problems:
1. LOJ: 1054
2. UVA: 13083

5. Function: Totient and Similar
Problems:
1. LOJ: 1007
2. SPOJ: NFACTOR , NDIV

6. Modular Arithmetic/CRT
Problems:
1. LOJ: 1067
2. CF: 687B, GYM100825A

7. Discrete Logarithms
Problems:
1. LOJ: 1325

8. Number Systems
Problems:
1. LOJ: 1028
2. E-OLYMP: 1001, 1002, 1008, 1013

9. Primitive Root
Problems:
1. E-OLYMP: 647

NB: This list is just created. And hopefully will grow with user contribution and as I learn. Thanks for being a part of it. :)

Contributors:
HaabyHings, Rudy1444, Lucas97, Batman, t3rminated, MladenP, TooNewbie

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

Comments Comments (24)
| Write comment?
»
8 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Since you are already at UVA, you would make use of UHunt. UHunt classifies UVA problems according to topic, and it is accessed right through the menu of the page.

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

    Yes, but I do not feel like the categories in UVA are sufficient. Let, I am learning Pell's equations now. Uhunt would list them as problems of GCD/LCM. I was horrified at least three times that how smart people are to solve this problem in a elegant way, until I found there are theory involved.

    And, thanks for your suggestion. People can use both if they want. :)

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

Diophantine Equations 7C

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

Please add to your list this search string:

http://codeforces.net/problemset/tags/number%20theory?order=BY_SOLVED_DESC

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

    Thanks for your suggestion. I wanted to add it, but that will defeat my purpose. I want this list to contain problems that fit in a specific category. Note, this list doesn't have to very big. It will contains problems that are almost purely number theoretical.

    One problem with search by tag is, say, a string algorithm problem has a feature that requires a gcd function also. Codeforces will tag this as both string and number theory. But, I do not expect somebody would learn number theory after covering almost all other concepts.

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

A nice number theory problem that includes a bit of probability too: http://codeforces.net/problemset/problem/711/E

And a CRT problem: http://codeforces.net/problemset/problem/687/B

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

    Thanks for your suggestion. 711E looks more like a counting problem. I want to exclude counting problems from number theory problems. If you are sure that it is a number theory problem please suggest the category it belongs to. I don't think I am capable of it ATM.

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

      Not too sure what you mean by counting problem. This problem is nice and teaches how to apply some basic number theory concepts.

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

        Ok, I have added 8 categories. Please suggest which category this problem belongs. Should I create another category for it?

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

          Divisibility/Primes/Co-prime/GCD/LCM i think. Creating categories for problems isn't always that good, since some problems fit more/none.

          Btw in contributors, my name shows as specialist, which triggers me, as my biggest fear in life is too fall to specialist again :D jk

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

            I don't think it's my fault. I just added your name. Color was automatically added by codeforces :(

            Trying to change your color. What can I do!

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

              Just remove and add his name again after January 10th, that's when the name color changes are back to normal.

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

            Why do you fear to be in the place you belong?

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

            I know the feel :|

            Cyan is the most aesthetically beautiful color out of all in CF (in my opinion), but I'd like to have a cyan handle through magic instead of by default :)

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

Problem A is almost an application of CRT. It also requires some other computations, but it is Number Theory.

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

For Primes/GCD/LCM part :

585E - Present for Vitalik the Philatelist

585C - Alice, Bob, Oranges and Apples

LCMSUMH

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

add these also — http://www.spoj.com/problems/NFACTOR/ , http://www.spoj.com/problems/NDIV/ — based on ETF

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

http://codeforces.net/gym/101212/attachments Problem B from the Bangladesh OI, uses prime factorization.

Two more problems, using logN factorization: 222C - Reducing Fractions and 546D - Soldier and Number Game.

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

There are some really good number-theory problems in e-olymp.

GCD and LCM: 1146 (easy), 1243 (easy), 1147 (normal), 1229 (normal), 1244 (normal), 1230 (hard)

Number systems: 1001 (easy), 1002 (normal), 1008 (normal), 1013 (hard)

Game theory: 1005 (easy), 1009 (normal), 7836 (hard)

Bonus really hard problem: 647 (extreme!)

Hint for 647:
→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by shakil.ahamed (previous revision, new revision, compare).

→ Reply