解題區/解題區 - UVa

UVa 11260 - Odd Root Sum

contents

  1. 1. Problem
  2. 2. Input
  3. 3. Output
  4. 4. Sample Input
  5. 5. Output for Sample Input
  6. 6. Solution

Problem

Given the value of an n you will have to find the modulo 100000000 value of the following expression:

floor(sqrt(1)) + floor(sqrt(3)) + floor(sqrt(5)) + ... + floor(sqrt(m)) , where m is the largest odd number not greater than n. Or in other words you will have to find the value of S where,

S = floor(sqrt(1)) + floor(sqrt(3)) + floor(sqrt(5)) + ... + floor(sqrt(m)) MOD 100000000

Input

The input file contains at most 30000 lines of inputs. Each line contains a single 64-nit signed integer which denotes the value of n. Input is terminated by a line containing a single zero which should not b processed.

Output

For each line of input produce one line of output. This line contains the value of S.

Sample Input

1
2
3
4
5
9
19
29
10000000
0

Output for Sample Input

1
2
3
4
9
26
49
38426378

Solution

先把前幾項列出來，會發現一個規律

1
2
3
4
5
6
7
8
11
22
3333
4444
555555
666666
77777777
...

每一次會增加兩個。

假設第 1 組為 11 22，第 2 組為 3333 4444 …
需要使用二分搜尋找到我們總共要幾組，然後直接利用公式算出來 sigma(2i * (2i - 1 + 2i))。

但是公式算出來後，會有一個 /3 需要出處理，這邊使用乘法反元素，幸好 3 和 100000000 有互質，不然還真是沒有辦法避免大數運算，計算的時候請各種小心 overflow 的問題。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <stdio.h> 
#include <math.h>
#include <algorithm>
using namespace std;
#define MOD 100000000 
long long inv(long long n, long long m) { // get n*? = 1 (mod m)
    long long la = 1, lb = 0, ra = 0, rb = 1;
    long long i = 0, t, mod = m;
    while(n%m) {
        if(!i) {
            la -= n/m*ra;
            lb -= n/m*rb;
        } else {
            ra -= n/m*la;
            rb -= n/m*lb;
        }
        i = !i;
        t = n, n = m, m = t%m;
    }
    if(i)
        return (la%mod+mod)%mod;
    return (ra%mod+mod)%mod;
}
long long getM(long long n) {
    long long l = 0, r = 3037000499LL/2, m, ret;
    long long tmp;
    while(l <= r) {
        m = (l + r) / 2;
        tmp = 4 * (m) * (m + 1);
        if(tmp <= n)
            l = m + 1, ret = m;
        else
            r = m - 1;
    }
    return ret;
}
int main() {
    unsigned long long n;
    long long inv3 = inv(3, MOD);
    while(scanf("%llu", &n) == 1 && n) {
        long long ret = 0;/*
		for(long long i = 1; i <= n; i += 2) {
			// printf("%d\n", (int)sqrt(i));
			ret += (long long) sqrt(i);
			ret %= MOD;
		}
		printf("%lld\n", ret);*/
        unsigned long long m = getM(n);
        long long prev = 4*(m)*(m + 1)%MOD*(2*m + 1)%MOD*inv3%MOD - m * (m + 1)%MOD;
        unsigned long long pn = 4 * (m) * (m + 1) - 1;
        prev = (prev%MOD + MOD)%MOD;
        //printf("%lld %lld %lld\n", m, prev, pn);
        m++;
        if(pn + m * 4 < n) {
            prev += (2 * m - 1) * 2 * m%MOD;
            pn += m * 4;
            //printf("CROSS1 %llu %llu\n", pn, prev);
            prev += (n - pn)/2 * 2 * m%MOD;
            //printf("CROSS2 %llu %llu\n", m * 2, (n - pn) /2);
        } else {
            prev += (n - pn)/2 * (2 * m - 1)%MOD;
            //puts("CROSS3");
        }
        printf("%llu\n", (prev%MOD + MOD)%MOD);
    }
    return 0;
}
/*
11
22
3333
4444
555555
666666
77777777
...
*/
/*
10000000001
*/