解題區/解題區 - Zerojudge

a962. 新專輯

contents

  1. 1. 題目
    1. 1.1. 內容：
    2. 1.2. 輸入說明：
    3. 1.3. 輸出說明：
    4. 1.4. 範例輸入：
    5. 1.5. 範例輸出：
  2. 2. 解法

題目

內容：

給定正整數N，請求出(N除以1的餘數)+(N除以2的餘數)+(N除以3的餘數)+…+(N除以N的餘數)。

輸入說明：

輸入只有一個正整數N，其中1<=N<=1014。

輸出說明：

為了避免要寫大數，你只要輸出這個奇怪的和除以1000000009的餘數就好了。

範例輸入：

10

範例輸出：

13

解法

  • 作法：
    各種方式要避免 mod 運算。
a962.cpp
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
/**********************************************************************************/
/*  Problem: a962 "新專輯" from TIOJ 1674                                      */
/*  Language: CPP (1612 Bytes)                                                    */
/*  Result: AC(0.8s, 272KB) judge by this@ZeroJudge                               */
/*  Author: morris1028 at 2014-04-18 20:11:19                                     */
/**********************************************************************************/
#include <stdio.h>
#include <math.h>
#define MOD 1000000009LL
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;
}
int main() {
    long long inv2 = inv(2, MOD);
    long long n;
    while(scanf("%lld", &n) == 1) {
        long long ret = 0, hret = 0;
        long long half = (long long)sqrt(n)/5;
        long long u = -1, v = 0;
        for(half = 1; u != v; half++, u = v, v = n/half) {
            hret += n%half;
        }
        hret -= n%(half - 1);
        hret %= MOD;
        long long l = half - 1, r, div;
        long long a0, d, tn, buff;
        while(l <= n) {
            div = n / l;
            r = n / div;
            a0 = n % l, d = -div, tn = r - l + 1;
            if(tn >= MOD)   tn %= MOD;
            if(d >= MOD)    d %= MOD;
            if(a0 >= MOD)   a0 %= MOD;
            buff = (a0 * 2 + (tn - 1)*d);
            if(buff < 0 || buff >= MOD) buff %= MOD;
            buff *= tn;
            if(buff < 0 || buff >= MOD) buff %= MOD;
            ret += buff;
            l = r + 1;
        }
        ret %= MOD;
        ret = (ret * inv2)%MOD;
        ret = (ret + hret + MOD)%MOD;
        printf("%lld\n", ret);
    }
    return 0;
}
/*
100000000000000
*/