Luogu P1829 [国家集训队]Crash的数字表格

题目链接: https://www.luogu.org/problemnew/show/P1829

显然,题目所求为以下式子

以下均默认$n \leq m$

$$
\sum_{i = 1}^n \sum_{j = 1}^m lcm(i,j)
$$

先来一些比较显然的东西
$$
\begin{aligned}
\sum_{i = 1}^n \sum_{j = 1}^m lcm(i,j) & =
\sum_{i = 1}^n \sum_{j = 1}^n \frac{i \cdot j}{\gcd(i,j)}\\
& = \sum_{d = 1}^n d \sum_{i = 1}^{\frac{n}{d}} \sum_{j = 1}^{\frac{m}{d}} i \cdot j \cdot [\gcd(i,j) = 1]\\
\end{aligned}
$$
后面一段看起来还可以再加优化

Continue reading “Luogu P1829 [国家集训队]Crash的数字表格”

Luogu P1403 [AHOI2005]约数研究

题目

实际上一开始看到题目我是打算写筛法的,后来发先是个除法分块秒切题目

显然

$$
\sum_{i = 1}^{n} f(i) = \sum_{i = 1}^{n} \lfloor \frac{i}{n} \rfloor
$$

除法分块即可

代码

#include <cstdio>

int n;
long long ans;

int main(){
    scanf("%d", &n);
    for(int left = 1, rig; left <= n; left = rig + 1){
        rig  = n / (n / left);
        ans += 1LL * (n / left) * (rig - left + 1);
    }
    printf("%lld", ans);
}


[CQOI2007]余数求和

题目

一开始老是把思路和做​ 和​ 弄混……

然后陷入思维死角,感谢题解把我拉了出来​

$$
\sum_{i = 1}^{n} k \mod i \
= \sum_{i=1}^{n} k – i \times \lfloor \frac{k}{i} \rfloor \
= n \times k – \sum_{i=1}^{n} i \times \lfloor \frac{k}{i} \rfloor​
$$

然后就是除法分块,这个转化是真的要命QAQ

代码

#include <cstdio>

long long n,k,ans=0;

inline long long Min(long long a,long long b){return a<b?a:b;}

int main(){
   scanf("%lld%lld",&n,&k);
   ans=n*k;
   for(long long l=1,r;l<=n;l=r+1){
       if(k/l!=0) r=Min(k/(k/l),n);
       else r=n;
       ans-=(k/l)*(r-l+1)*(l+r)/2;
  }
   printf("%lld",ans);
}