water

Posted on Edited on In

题目大意：给定数字n，求\(n\bmod i\)和，其中i属于n，多组数据T1e6,n1e7！

显然可以数论分块，对于每个块，如果发现跨度大于1，那么这个序列贡献出来的答案就是一个等差数列，然后算就完事了

时间复杂度：\(O(T\times \sqrt n)\)

还可以推数学式子，但是我不会

于是我们再次打表找规律，就看每个数字对于后面数的贡献是啥，栗子：

1对谁也没有贡献，2对2贡献为0，对3贡献为1,3对3贡献为0，对4贡献为1，对5贡献为2，对6贡献为零…

打个表就会发现，我们设\(f_i\)表示答案

显然可以发现\(f_i=f_{i-1}+(i-2)-(d_i-1-i)\)（d表示i的约数和）

显然从上一个数字当当前，是每一位的贡献都会多（除了i和本身）所以加上i-2

但是我们又可以打表发现这个数字的下面的约数位都是0，也就是我们一定多加了某些数字，所以要减去约数和，但是约数和包含了1和i

所以还要加回来

但是我不会线性筛约数和，回头补坑

代码如下：（注释部分即为整除分块）

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
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int N = 1e7 + 66;

int T, n;
bool vis[N];
int f[N], prime[N], cnt;
long long sum[N], tot[N];

void pres_dou()
{
    cnt = 0;
    sum[1] = 1;
    for (int i= 2; i < 1e7; ++ i)
    {
        if (! vis[i]) prime[++ cnt] = i, sum[i] = i + 1, tot[i] = i + 1;
        for (int j = 1; j <= cnt && i * prime[j] < N; ++ j)
        {
            vis[i * prime[j]] = 1;
            if (!(i % prime[j]))
            {
                tot[i * prime[j]] = tot[i] * prime[j] + 1;
                sum[i * prime[j]] = sum[i] / tot[i] * tot[i * prime[j]];
                break;
            }
            sum[i * prime[j]] = sum[i] * sum[prime[j]];
            tot[i * prime[j]] = 1 + prime[j];
        }
    }
}

signed main()
{
/*
    T = read();
    while (T --)
    {
        int i, l, r; n = read(), res = 0;
        for (l = 1; l <= n; l = r + 1)
        {
            r = n / (n / l);
            if (r == l) res += n % l;
            else
            {
                int t = n / l, len = r - l + 1, a1 = n % r;
                res += 1ll * len * a1 + 1ll * len * (len - 1) / 2 * t;
            }
        }
        put(res);
    }
*/
    pres_dou();
    T = read();
    f[3] = f[4] = 1;
    for (int i = 5; i <= 1e7; ++ i) f[i] = f[i - 1] + i - 2 - (sum[i] - 1 - i);

    while (T --)
    {
        n = read();
        put(f[n]);
    }
    fclose(stdin), fclose(stdout);
    return 0;
}
/*
给定数字n
求n/i的余数的和，其中i属于n
*/

总结：

今天上午期望得分：60+10+0+50=120pts

实际得分：20+40+0+50=110pts

第一题挂掉令人惊讶，第二题输出1得了四十分更令人惊讶

最令人惊讶的是第四题竟然是个直接暴力的水题

今天下午期望得分：10+40+20+30=100pts

实际得分：20+40+20+30=110pts

出题人良心，不然不可能过百

其实考了这么多这么多回，知识的提高并不是显著的，显著的是我明显感觉到我的做题策略终于改变了

部分分和暴力分数几乎做到颗粒归仓

人都是顽固不化的，考了三个月我才领悟到考试的精髓，考了三个月才从那种上来就干正解的傻逼策略中扭转过来

看起来很可笑

但是当人真正处于围城的时候，无法自拔，深陷其中，无数次怀疑自己的能力而不是自己的方法

更没有怀疑过自己的做题策略这种小小小的细节

但是就是这种小小小的细节决定了我的成败

我可以不如别人厉害，但是我不一定考的分数比别人低

推荐名额定了，不出所料，但又略有失望

假如我可以早一个月扭转做题策略，我未尝不可被推荐，拿到一种毫无压力的通往NOIp的门票

但是那是假如

悟已往之不谏 知来者之可追