Codeforces will not be available in the period 01:00-05:00 May, 30 (MSK, UTC +3) because of maintenance. ×

### Polar_'s blog

By Polar_, history, 2 months ago, ,

Hi! I need help in calculating $\sum\frac{1}{n^2}\%MOD$.
Where $MOD$ is a prime number .
I know that taking of inverse modulo for every $k^2$ where $1 \le k \le n$ then adding them up and taking modulo.
But if $n$ is order of $10^9$ then how to do it ?
Any faster way to do it ?
Thanks .

• +6

 » 2 months ago, # | ← 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
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 Can you please elaborate ?Try this n = 5 and mod = 7 . I think the answer will be 6 .
•  » » 2 months ago, # ^ |   0 Your $S$ isn't an integer, but a real number. Your formula gives a real number as the result, not an integer.
•  » » » 2 months ago, # ^ | ← Rev. 2 →   0 Yeah Xellos You are right .
•  » » » 2 months ago, # ^ |   0 if n = 5, and mod = 7 then S = 1 / 1 + 1 / 4 + 1 / 9 + 1 / 16 + 1 /25 % 7But 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
•  » » » » 2 months ago, # ^ |   0 $S = 5269/3600 = 6$ because $3600 \cdot 6 = 5269$ modulo $7$. Read about modular division.
•  » » » » » 2 months ago, # ^ |   -8 I thought the formula to calculate S was S = 1 / 1 ^ 2 + 1 / 2 ^ 2 + 1 / 3 ^ 2 + ... + 1 / n ^ 2
•  » » » » » » 2 months ago, # ^ |   0 $1/1^2 + 1/2^2 + 1/3^2 + 1/4^2 + 1/5^2 = 5259/3600$, just use a calculator...
•  » » » » » » » 2 months ago, # ^ |   -8
•  » » » 2 months ago, # ^ |   +8
•  » » » » 2 months ago, # ^ |   0 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.
 » 2 months ago, # |   0 How large can $MOD$ be?
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 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.
•  » » » 2 months ago, # ^ |   0 Mod can be 1e9 + 7 .
 » 2 months ago, # |   +18 The answer is$\frac{\pi^2}{6} \mod p$Seriously, maybe this sum can be simplified if you express its summands as degrees of some primitive root.
•  » » 2 months ago, # ^ |   0 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.
•  » » » 2 months ago, # ^ |   0 You can It was a joke about the poor problem statement.
•  » » » » 2 months ago, # ^ |   0 I considered the possibility that it was a joke, but I wasn't sure...
 » 2 months ago, # |   0 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.
•  » » 2 months ago, # ^ |   0 Thanks .
•  » » 7 weeks ago, # ^ |   0 i didnt get it exactly. can you please explain it bit more or give any link where i could study this topic?
 » 7 weeks ago, # | ← Rev. 2 →   +11 You can precompute each sum with step $10^6$. On ideone for range $10^7$ runtime is $1.32$ seconds, then for $10^9$ runtime is $132$ seconds (two minutes). Now you know each sum with step $10^6$ and can copy-paste array into code. So, you can find any required sum with precalculated values by addition at most $10^6$ terms.