| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3845 |
| 2 | jiangly | 3707 |
| 3 | Benq | 3630 |
| 4 | orzdevinwang | 3573 |
| 5 | Geothermal | 3569 |
| 5 | cnnfls_csy | 3569 |
| 7 | jqdai0815 | 3532 |
| 8 | ecnerwala | 3501 |
| 9 | gyh20 | 3447 |
| 10 | Rebelz | 3409 |
| Страны | Города | Организации | Всё → |
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 171 |
| 2 | adamant | 163 |
| 3 | awoo | 162 |
| 4 | nor | 153 |
| 5 | maroonrk | 152 |
| 6 | -is-this-fft- | 151 |
| 7 | TheScrasse | 150 |
| 8 | atcoder_official | 145 |
| 8 | Petr | 145 |
| 10 | pajenegod | 144 |
Why is 1000000007 harmful?
Think it is easier to make mistake in number of zeroes when typing. (I use
1000 * 1000 * 1000 + 7)Either copy paste from the problem statement or write (int)(1e9 + 7).
I agree, just trying to explain why that modulo might be harmful.
(int)(1e9 + 7) is bad. Use (int)1e9 + 7.
const int x = 1e9 + 7; works pretty fine because no conversion needed for precise doubles.
in c++14 you can write
Once, in a hurry, I used a combination of two:
1000 * 000 * 000 + 7I think it is easier to remember and write (int)1e9 + 7 than remembering this weird number 1000999777. In any case you will have to copy + paste.
Maybe the original title was "An alternative to 1000000007 modulo", but... Niklaus Wirth had much better suggestion.
Those pioneers used to take important things like titles seriously. Nowadays you typically get something meaningless. Sometimes even with spelling errors. Not exaggerating — I saw one in a keynote slide title last year.
Not as harmful, as 1000000009)
Which is still not as harmful as 1234567891 (yes, it's prime).
Which is still not as harmful as 1000696969... Just kidding, awesome, easy prime ^^
1000696969 does not cause integer overflow when you try to add two residues.
( ͡° ͜ʖ ͡°)
it could cause some other issues! imagine what printf looks like with that! it better too use typedef. Also I failed in system testing once because o using long long instead of int! so this is harmful too! ;)
lewd
Why is it so? Just curious.
Because 10^9+7 is used in most of the problems and when 10^9+9 occur a lot of contestants don't pay attention and still use 10^9+7.
Note that choice of p = 1 000 000 007 is not random. Not only is it the smallest prime larger than 109, but also p - 1 is a semiprime (its only prime divisors are 2 and 500 000 003).
There are some techniques exploiting the factorization of p - 1 (for example, it has very many 2s in its prime factorization or has no large prime divisors). And... The largest prime divisor of 1 000 999 777 - 1 is only 317.
I wonder if that's because if we multiply any n from [1, p) by any m from [1, p), then (n*m) % p is never a zero? Making that a closed set under multiplication, of size p-1.
I guess I haven't appreciated all the virtues of 1 000 000 007. While I don't think that it would have much direct effect if occasionally somebody got points for designing a scheme to exploit that weakness (I'm assuming that it's not bad enough such that every solution using addition and multiplication mod p would be automatically exploitable...), but the secondary effects seem undesirable. Such as: problemsetters having to worry about such things; strong contenders spending time perfecting such techniques to get the odd advantage, while they could be learning something useful; and the general public awareness that this is a source of weakness, and any mention of weakness is bad, due to the Chinese whispers effect.
I've looked up 1 000 000 007 before posting the original memo, but none of the answers dealing with what's special about it mentioned anything other than the ramifications of it being a prime. This shows once again that the best way of asking a question is by making a provocative suggestion.
Yup, this kind of weaknesses come out from what you said — nonzero residues mod p create a group under multiplication of order p - 1.
You told that strong contestants might want to look for some properties of moduli they get. I'll tell you what I do when I see a prime p different than 109 + 7 and 109 + 9: I automatically open my terminal, run 'factor p' and 'factor p-1' and check if something interesting happens — no learning weird techniques. Still, as for me, it's better to be safe than sorry.
As for people trying to take advantage of bad modulus: if you choose a random prime, most probably nobody will exploit it. However, I have never heard of a solution noticing that 'blah, blah, 1 000 000 007 has some special property, so we can do blah blah blah and we're done' (I'm aware that some funny properties can be found, but as for now I don't know any).
Moreover, I (and surely you) have already seen a few solutions exploiting weird things about other primes — but none of them seemed extendable to the case of our 'beloved' prime xD.
I must have been the first to expose the cult of 1000000007 and its evil twin 1000000009 by drawing attention to their inconvenient truth: that nobody can read them without digit separators. And not everybody is aware that int(1e9 + 7) is safe to do (with evidence even on this page).
Though I agree that right now, after thousands of problems using 1000000007, seeing something else suggests that it has a special property that needs to be used (like properties of digital roots of certain numbers in that field, or something to do with the FFT). This shouldn't be a problem for simpler questions however, targeted at newcomers, where the hypnotising nature of 1000000007 becomes a bigger problem.
Briefly, define a competition prime as a prime P between 9e8 and 2**30, such that both P and (P-1)/2 are primes. After a search, I'm pretty sure there aren't any highly readable numbers among the competition primes. The best I could find are probably 1000111787, 1060777919 and 1007111999.
Found a better one: 999119999 (check: http://www.wolframalpha.com/input/?i=Factorise+%28%28999119999-1%29%2F2%29+%2A+999119999 ).
Or this one: 1000992299 (check: http://www.wolframalpha.com/input/?i=Factorise+%28%281000992299-1%29%2F2%29+%2A+1000992299 ).
By the way, the correct terminology is safe primes (and the smaller (p-1)/2 prime is called a Sophie Germain prime).
The case that algorithmic competitions should use safe primes as the modulus is clear.
There are also cryptographically strong primes of various types, corresponding to additional conditions on ((p-1)/2)-1 having a large prime factor, p+1 having a large prime factor, and even the latter factor minus one having a large prime factor... But that's from cryptography's point of view, where the requirements are to be strong against particular factoring algorithms. In our case, the requirement is to prevent an arbitrary problem from being decomposable into versions mod small numbers, which may then admit much simpler solutions.
Actually, the largest factor of 1 000 000 007+1 is only 167, but it seems that designing a way to exploit this fact in your typical DP problem is still up for grabs.
If given number is not a prime, you'll need to use Euler Totient Function to use modular multiplicative inverse. Other uses are mentioned
I think a competitive programming problem should not require knowledge about some hard arithmetic theorems. Those would rather fit the syllabus of IMO, IMO.
That's in reply to something that only considers primes??
If you are a problemsetter and you are writing a problem where you do computation modulo p, it is recommended to include an example where the result is obvious and the modulo actually gets used. E.g., "Here the answer is obviously 2^40, so you should return 2^40 mod 1,000,000,007 = 511,620,083.". This doesn't give away the solution and it prevents typos.
Obviously, there are some problems where this cannot be done, but often it's possible to find a test case that's large but simple enough.
Yeah, someone I know(I'd just mention he's red here) wasn't fully aware how dangerous it was... he failed in regional round of KOI(Korean OI) last year. I hope he do well in IOI next week! ;)
Yes, It was cruel.
Auto comment: topic has been updated by EvgeniSergeev (previous revision, new revision, compare).
what about FFT-friendly primes? Pretty ones I was able to find between 109 and 1010:
adding two 'int' type integers under 2003304449 can cause overflow.
well, then, what about
Which is why we have long long :D