题解 UVA12546 【LCM Pair Sum】

huyufeifei · 2018-12-12 20:28:00 · 题解

题意：以质因数分解的方式给定n，求所有满足：lcm(a, b) = n的无序数对的价值和。其中(a, b)的价值为a + b

首先考虑只有一个质因数，例如4。

有如下数对：(1, 4), (2, 4), (4, 4)

可得答案为1 + 2 + 4 + 4^3

然后扩展：6。

对于每个质因数来说：

2: (1, 2), (2, 2)

3: (1, 3), (3, 3)

两两乘起来之后发现：少了一项(2, 3)，这是由于我们用的是无序数对。那么改成有序数对试试。

     2:        3:

    (1, 2)    (1, 3)

    (2, 1)    (3, 1)

    (2, 2)    (3, 3)

交叉相乘：

    (1, 6) (3, 2) (3, 6)

    (2, 3) (6, 1) (6, 3)

    (2, 6) (6, 2) (6, 6)

发现所有无序数对除了(6, 6)之外都出现了两次，于是补上一个(6, 6)之后/2即可。

现在考虑如何求交叉相乘的表的总和。

设我们的两列数对如下：

    (a, b)    (e,f)

    (c, d)    (g, h)

要求的式子：

因式分解：

考虑我们一开始列出来的某一列：

    2：

    (1, 2)

    (2, 1)

    (2, 2)

可得：a + c = b + d

故上式 = 2(a + c)(e + g)

定义首项为a，公比为q，项数为n的等比数列的和为getQ(a, q, n)

推广：

设n = Πai^pi，则ans = 2Π{getQ(1, ai, pi + 1) + pi * ai^pi}

时间复杂度TmlogV，其中V为指数值域。

代码：

#include <cstdio>

typedef long long LL;
const int N = 17;
const LL MO = 1e9 + 7;

int a[N], p[N];

inline LL qpow(LL a, LL b) {
    LL ans = 1;
    while(b) {
        if(b & 1) {
            ans = ans * a % MO;
        }
        a = a * a % MO;
        b = b >> 1;
    }
    return ans;
}

inline LL getQ(LL a, LL q, LL n) {
    a %= MO;
    if(!n) {
        return 0ll;
    }
    if(n == 1 || !a || !q) {
        return a;
    }
    if(n == 2) {
        return (a + a * q % MO) % MO;
    }
    if(n & 1) {
        return (a + getQ(a * q % MO, q, n - 1)) % MO;
    }
    return (qpow(q, n >> 1) + 1) * getQ(a, q, n >> 1) % MO;
}

inline void solve() {
    int n;
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        scanf("%d%d", &a[i], &p[i]);
    }
    LL ans = 2, sum = 1;
    for(int i = 1; i <= n; i++) {
        LL temp = qpow(a[i], p[i]) * p[i] % MO;
        (temp += getQ(1, a[i], p[i] + 1)) %= MO;
        ans = ans * temp % MO;
        (sum *= qpow(a[i], p[i])) %= MO;
        //printf("temp : %lld \n", temp);
    }
    //printf("sum = %lld \n", sum);
    ans = (ans + sum + sum) % MO;
    ans = ans * ((MO + 1) >> 1) % MO;
    printf("%lld\n", ans);
    return;
}

int main() {

    int T;
    scanf("%d", &T);
    for(int i = 1; i <= T; i++) {
        printf("Case %d: ", i);
        solve();
    }

    return 0;
}