Richard Liu
Richard Liu

Sol: Leo and the MO Problem

Problem Link: http://oj.hecz.info:4000/problem/2
As the problem instructs, you are supposed to solve this function.
S_n = \sum_{k=1}^{n} \left[ \dfrac{(3k+6)!+1}{3k+7} – \left[ \dfrac{(3k+6)!}{3k+7} \right] \right]

Let’s take a look at it, considering the Wilson’s theorem, which says:

Only when p is a prime, ( p -1 )! ≡ -1 (\mod p )

It’s no hard to see the regular patterns, as you have to count all the primes in advance.

void getprime(int n) {
    for (int i = 2; i <= n; ++i) {
        if(used[i] == 0) prime[++tot]=i;
        for(int j = 1; j <= tot; ++j) {
            if (prime[j] * i > n) break;
            used[prime[j] * i] = 1;
            if (i % prime[j] == 0) break;
        }
    }
}

Then it’s the final program.

getprime(MAXN);
ans[0] = 0;
ans[1] = 0;
for (int i = 2; i <= 1e6; ++i) ans[i] = ans[i - 1] + !(used[3 * i + 7]); 

Leave a Reply

textsms
account_circle
email

Richard Liu

Sol: Leo and the MO Problem
Problem Link: http://oj.hecz.info:4000/problem/2 As the problem instructs, you are supposed to solve this function. $$S_n = \sum_{k=1}^{n} \left[ \dfrac{(3k+6)!+1}{3k+7} - \l…
Scan QR code to continue reading
2021-08-12