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);