interestingLSY 的博客

interestingLSY 的博客

题解 P1447 【[NOI2010]能量采集】

posted on 2018-08-13 23:22:59 | under 题解 |

① 抽象为模型:

就是给你一个 $n\cdot m$ 的方阵,问每个点与原点的连线中有多少点(不包括两头的)*2+1再求和,

形式化地说,就是求

$$\color{blue}\sum_{i=1}^{n}\sum_{j=1}^{m}gcd_{i,j}\cdot2-1$$

注意是减,因为我们不计算这条线段两端点

即为

$$\color{blue}\left[\sum_{i=1}^{n}\sum_{j=1}^{m}gcd_{i,j}\right]\color{black}\cdot2\ -\ nm$$

好现在的主要矛盾就是求蓝色那部分.

② 开始乱搞

正向不好求,我们考虑暴力(顺便说一句,这题暴力求上面式子有 $\color{green}80$ 分qwq)反着求,即

开一个 $cnt$ 数组, $cnt_i$ 表示公约数为i的数对个数.(注意不是最大公因数)

显然根据乘法原理,

$$\color{Blue}cnt_i = \left\lfloor\frac{n}{i}\right\rfloor+\left\lfloor\frac{m}{i}\right\rfloor$$

但是我们忽略了一点,就是一个数对可以产生公因数 $x$ ,也可能产生公因数 $2x,3x......$

所以咋整?减掉就行!

Code:

注意一点:最终减掉 $nm$ 时要减去1LL*n*m,不然会爆

(只贴出关键部分)

    Read(n,m);
    For(i,max(n,m))
        cnt[i] = 1LL * (n/i) * (m/i);
    fOR(i,max(n,m)){
        int x = i+i;
        g[i] = cnt[i];
        while( x <= max(n,m) ){
            g[i] -= g[x];
            x += i;
        }
    }
    For(i,max(n,m))
        ans += 1LL * i * g[i];

    printf("%lld",ans*2LL-1LL*n*m);