P7788 [COCI2016-2017#6] Savrsen 题解

tuxuanming2024 · 2021-08-30 09:35:42 · 题解

这题如果暴力求每个数的因数肯定会爆，于是我们可以用类似埃及筛法的思想去做。

枚举 [1,b] 之间的数 i ，那么 i 一定是 i 倍数的因数，所以我们枚举 j ，在 i \times j 的因数中加上 i ，最后 [a,b] 循环依次累加“不完美值”即可。

code:

#include <iostream>
#include <cmath>
using namespace std;
long long a,b,s[10000005],ans;
int main()
{
    cin>>a>>b;
    for(int i=1;i<=b;i++)
        for(int j=2;i*j<=b;j++) s[i*j]+=i;
    for(int i=a;i<=b;i++) ans+=abs(i-s[i]);
    cout<<ans;
    return 0;
}