http://www.codechef.com/IOPC2014/problems/IOPC14A
What is the way to solve this problem? Most of solutions seems to check (n!mod (2*b))>=b or not ,whats the reason for this?
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 4009 |
2 | jiangly | 3839 |
3 | Radewoosh | 3646 |
4 | jqdai0815 | 3620 |
4 | Benq | 3620 |
6 | orzdevinwang | 3612 |
7 | Geothermal | 3569 |
8 | ecnerwala | 3494 |
9 | Um_nik | 3396 |
10 | gamegame | 3386 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | Um_nik | 164 |
2 | maomao90 | 163 |
3 | -is-this-fft- | 162 |
4 | atcoder_official | 158 |
4 | cry | 158 |
4 | awoo | 158 |
7 | nor | 155 |
7 | adamant | 155 |
9 | TheScrasse | 153 |
10 | maroonrk | 152 |
http://www.codechef.com/IOPC2014/problems/IOPC14A
What is the way to solve this problem? Most of solutions seems to check (n!mod (2*b))>=b or not ,whats the reason for this?
Название |
---|
You can calc the power of 2 in n!(it's n/2+n/4+n/8+...) and power of 2 in b(just divide it by 2 while n%2=0) and compare this values
vintage_Vlad_Makeev your idea is wrong probably because it's integer division. For eg:
a) 12 = 22 * 3 , 8 = 23, (12 / 8 = 1) % 2 = 1
b) 20 = 22 * 5 , 8 = 23, (20 / 8 = 2) % 2 = 0
But powers of 2 in (12, 8) and (20, 8) are same. You could find a similar case for factorials as well.
Each student gets n! / b (integer division) oranges. If n!%(2b) is less than b, then it can be written as 2*k*b + r for some integer k and r < b. Then n!/b is equal to 2*k, so each student gets an even number of oranges. If n!%(2b) is >= b, then it can be written as 2*k*b + r where b <= r < 2*b, or 2*k*b + b + r', where r' = r — b, so 0 <= r' < b. Then, (2*k*b + b + r')/b = 2*k + 1, which is odd.
one more doubt
The above code seems to be finding (a*b)%m ,but we can do directly right .then why coders do so?
Doing it directly could result in overflow.
but can (a%m)*(b%m)%m cause overflow?
Yes because they can both be up to m-1, and m can be up to 10^18
u r so fast in helping ,ty
one more doubt if i dont write long double it gives wa ~~~~~ (long long)((long double)a * (long double)b / (long double)m); ~~~~~
and
whats difference
Long doubles are more precise than doubles, and long longs have a higher range of values than longs.