bzoj3114 LCM Pair Sum

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

解：

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

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

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

可得答案为getQ(1, 2, 2) + 4³

然后扩展：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)

要求的式子：

ae + bf + ag + bh + ce + df + cg + dh

因式分解：

(a + c)(e + g) + (b + d)(f + h)

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

2：

(1, 2)

(2, 1)

(2, 2)

可得：a + c = b + d

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

推广：

设n = Πa_i^p_i，则ans = 2Π{getQ(1, a[i], p[i] + 1) + p_i * a_i^p_i}

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

 #include <cstdio>

 typedef long long LL;

 const int N = ;

 const LL MO = 1e9 + ;

 int a[N], p[N];

 inline LL qpow(LL a, LL b) {

     LL ans = ;

     while(b) {

         if(b & ) {

             ans = ans * a % MO;

         }

         a = a * a % MO;

         b = b >> ;

     }

     return ans;

 }

 inline LL getQ(LL a, LL q, LL n) {

     a %= MO;

     if(!n) {

         return 0ll;

     }

     if(n ==  || !a || !q) {

         return a;

     }

     if(n == ) {

         return (a + a * q % MO) % MO;

     }

     if(n & ) {

         return (a + getQ(a * q % MO, q, n - )) % MO;

     }

     return (qpow(q, n >> ) + ) * getQ(a, q, n >> ) % MO;

 }

 inline void solve() {

     int n;

     scanf("%d", &n);

     for(int i = ; i <= n; i++) {

         scanf("%d%d", &a[i], &p[i]);

     }

     LL ans = , sum = ;

     for(int i = ; i <= n; i++) {

         LL temp = qpow(a[i], p[i]) * p[i] % MO;

         (temp += getQ(, a[i], p[i] + )) %= 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 + ) >> ) % MO;

     printf("%lld\n", ans);

     return;

 }

 int main() {

     int T;

     scanf("%d", &T);

     for(int i = ; i <= T; i++) {

         printf("Case %d: ", i);

         solve();

     }

     return ;

 }

AC代码

题外话：这东西是我在某个最小割练习题表里面看到的......

巴特西

bzoj3114 LCM Pair Sum

最新文章

热门文章