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
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.
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. :)
Diophantine Equations 7C
Added. Thank you
Please add to your list this search string:
http://mirror.codeforces.com/problemset/tags/number%20theory?order=BY_SOLVED_DESC
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.
A nice number theory problem that includes a bit of probability too: http://mirror.codeforces.com/problemset/problem/711/E
And a CRT problem: http://mirror.codeforces.com/problemset/problem/687/B
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.
Not too sure what you mean by counting problem. This problem is nice and teaches how to apply some basic number theory concepts.
Ok, I have added 8 categories. Please suggest which category this problem belongs. Should I create another category for 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
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!
Just remove and add his name again after January 10th, that's when the name color changes are back to normal.
Why do you fear to be in the place you belong?
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 :)
Problem A is almost an application of CRT. It also requires some other computations, but it is Number Theory.
For Primes/GCD/LCM part :
585E - Present for Vitalik the Philatelist
585C - Alice, Bob, Oranges and Apples
LCMSUMH
Added! But, Maybe the codeforces is facing some bugs. The color in the contribution list is not correct. :(
It's New Year, right? They allow us "magic" to change color.
Can you please give any hint on how to solve LCMSUMH
add these also — http://www.spoj.com/problems/NFACTOR/ , http://www.spoj.com/problems/NDIV/ — based on ETF
http://mirror.codeforces.com/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.
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!)
Think about primitive root...
Auto comment: topic has been updated by shakil.ahamed (previous revision, new revision, compare).
**Thank you **