Difference between revisions of "Training 4: Number Theory"

From EOJ Wiki
Jump to navigation Jump to search
(Created page with "=== Problem A ===")
 
Line 1: Line 1:
 
=== Problem A ===
 
=== Problem A ===
 +
 +
题意: $\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}lcm(i,j)$
 +
 +
题解: 原式=$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\frac{i \times j}{gcd(i,j)} = \sum\limits_{k=1}^{n}k\sum\limits_{i=1}^{\frac{n}{k}}\sum\limits_{j=1}^{\frac{m}{k}}i \times j[gcd(i,j)=k]$ 然后莫比乌斯反演得$\sum\limits_{k=1}^{n}mu[i] \times (1+...+\frac{n}{k}) \times (1+...+\frac{m}{k})$ 然后数论分块求和

Revision as of 13:43, 12 May 2019

Problem A

题意: $\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}lcm(i,j)$

题解: 原式=$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{m}\frac{i \times j}{gcd(i,j)} = \sum\limits_{k=1}^{n}k\sum\limits_{i=1}^{\frac{n}{k}}\sum\limits_{j=1}^{\frac{m}{k}}i \times j[gcd(i,j)=k]$ 然后莫比乌斯反演得$\sum\limits_{k=1}^{n}mu[i] \times (1+...+\frac{n}{k}) \times (1+...+\frac{m}{k})$ 然后数论分块求和