Блог пользователя EvgeniSergeev

Автор EvgeniSergeev, история, 9 лет назад, По-английски

Suggested upgrade: 1000999777 (prime)


Update. See below for why this is not an ideal candidate.

However, either of the following should be just as good as 1000000007:

  • Проголосовать: нравится
  • +49
  • Проголосовать: не нравится

»
9 лет назад, # |
  Проголосовать: нравится +58 Проголосовать: не нравится

Why is 1000000007 harmful?

»
9 лет назад, # |
  Проголосовать: нравится +71 Проголосовать: не нравится

Not as harmful, as 1000000009)

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Which is still not as harmful as 1234567891 (yes, it's prime).

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Which is still not as harmful as 1000696969... Just kidding, awesome, easy prime ^^

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        1000696969 does not cause integer overflow when you try to add two residues.

        • »
          »
          »
          »
          »
          9 лет назад, # ^ |
            Проголосовать: нравится +5 Проголосовать: не нравится
          #define int long long
          

          ( ͡° ͜ʖ ͡°)

          • »
            »
            »
            »
            »
            »
            9 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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! ;)

          • »
            »
            »
            »
            »
            »
            9 лет назад, # ^ |
              Проголосовать: нравится +11 Проголосовать: не нравится
            #define long long long
            
      • »
        »
        »
        »
        7 лет назад, # ^ |
          Проголосовать: нравится +5 Проголосовать: не нравится

        lewd

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Why is it so? Just curious.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
9 лет назад, # |
Rev. 2   Проголосовать: нравится +93 Проголосовать: не нравится

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.

  • »
    »
    9 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    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.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится +13 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        9 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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.

    • »
      »
      »
      9 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

»
9 лет назад, # |
  Проголосовать: нравится +82 Проголосовать: не нравится

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.

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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! ;)

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

»
9 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

what about FFT-friendly primes? Pretty ones I was able to find between 109 and 1010:

2003304449 = 2^19 * 3821 + 1
3221225473 = 2^30 * 3 + 1