How to calculate summation 1/(n^2) with modulo prime number .

4 года назад, # |

← Rev. 3 →

-18

[Wrong approach]

If I dont understand wrong. just calculate S = the total sum of 1 / k^2 for every 1 ≤ k ≤ n in O(sqrt(n))

Then the result will be S % MOD = S — floor(S / MOD) * MOD

→ Ответить

4 года назад, # ^ |

← Rev. 2 →

Can you please elaborate ?
Try this n = 5 and mod = 7 . I think the answer will be 6 .

→ Ответить

4 года назад, # ^ |

Your $$$S$$$ isn't an integer, but a real number. Your formula gives a real number as the result, not an integer.

→ Ответить

4 года назад, # ^ |

← Rev. 2 →

Yeah Xellos You are right .

→ Ответить

4 года назад, # ^ |

if n = 5, and mod = 7 then

S = 1 / 1 + 1 / 4 + 1 / 9 + 1 / 16 + 1 /25 % 7

But why the result is 6 ? How to calculate the modulo of real number, I thought module result something left when remove the biggest number smaller than N and divides MOD

→ Ответить

4 года назад, # ^ |

$$$S = 5269/3600 = 6$$$ because $$$3600 \cdot 6 = 5269$$$ modulo $$$7$$$. Read about modular division.

→ Ответить

4 года назад, # ^ |

-8

I thought the formula to calculate S was S = 1 / 1 ^ 2 + 1 / 2 ^ 2 + 1 / 3 ^ 2 + ... + 1 / n ^ 2

→ Ответить

4 года назад, # ^ |

$$$1/1^2 + 1/2^2 + 1/3^2 + 1/4^2 + 1/5^2 = 5259/3600$$$, just use a calculator...

→ Ответить

Sorry, I used google calculator and it give wrong answer

4 года назад, # ^ |

-8

→ Ответить

Oh I found the blog talk about real number modulo

4 года назад, # ^ |

→ Ответить

4 года назад, # ^ |

You can't define modulo for a general real number except perhaps as "subtract/add mod until you get a number in [0, mod)", which isn't an integer. You can make some sort of definition in special cases, e.g. $$$\sqrt{x} \equiv y$$$ if $$$y^2 = x$$$ modulo $$$mod$$$, but this has its own problem, most importantly non-uniqueness, which makes it much more impractical as a hash to check correctness in a contest. Multiplicative inverse has no such problems, coprimality guarantees nice properties.

→ Ответить

v-O_O-v

4 года назад, # |

How large can $$$MOD$$$ be?

→ Ответить

v-O_O-v

4 года назад, # ^ |

← Rev. 2 →

I wrote a brute-force solution and printed out the result (($$$1 / i^2$$$)%$$$MOD$$$) for each $$$i$$$ until $$$n$$$ and found out that the values are cyclically repeated with cycle length equal to $$$MOD$$$. So if you calculate just one cycle and store it in an array you can get the final result easily.

Please correct me if I am wrong.

→ Ответить

4 года назад, # ^ |

Mod can be 1e9 + 7 .

→ Ответить

alexyz

4 года назад, # |

+18

The answer is

Seriously, maybe this sum can be simplified if you express its summands as degrees of some primitive root.

→ Ответить

4 года назад, # ^ |

How do you compute an irrational number modulo a prime? I think he means $$$\sum_{n=1}^N \frac{1}{n^2}$$$, that's a rational number.

→ Ответить

alexyz

4 года назад, # ^ |

You can
It was a joke about the poor problem statement.

→ Ответить

4 года назад, # ^ |

I considered the possibility that it was a joke, but I wasn't sure...

→ Ответить

4 года назад, # |

Here's an idea: the sum for even $$$n$$$ is $$$\frac{1}{4}\sum_{n=1}^{N/2} \frac{1}{n^2}$$$, the rest is the sum for odd $$$n$$$. This way, you can split the sum based on the smallest few primes in the decomposition of $$$n$$$ in the summands. There aren't that many primes below $$$10^9$$$ and small enough sums can be precomputed, so this could give a decent runtime.

Also note that $$$(ab)^{-1} = a^{-1} \cdot b^{-1}$$$, which saves a lot of time spent on computing modular inverses.

→ Ответить