UVALive 5964 LCM Extreme 数论、LCM、筛选

LCM Extreme 数论、LCM、筛选

Source

UESTC 2016 Summer Training #11 Div.2

UVALive 5964

My Solution

让人想起素数筛选算法， 还是挺像的

sum[i]表示与i互质 且比i小的数之和，那么sum[i] = (1+i)*i/2 - ∑sum[i/d] (其中d是i的所有非1约数)

//集训的时候只想到这里，后面的没主意怎么处理了

//下面是搜索来的

ans[n] = ans[n-1] + ∑sum[n/d]*d*n/d(其中d是n的所有约数)

sum[n/d]所求的和的那些数肯定和n是互质的，那么的话他们乘上d与n求gcd的话肯定就是d了，那么他们和n求lcm的话就是sum[n/d] * d(最大公约数) * n/d了，这个也是可以通过筛素数的方式地推出来的。

复杂度 O(n*log(n) + T)

#include 
#include 
#include 
using namespace std;
typedef unsigned long long unsLL;
const unsLL maxn = 5*1e6 + 8;


unsLL sum[maxn], ans[maxn];

int main()
{
    #ifdef LOCAL
    freopen("a.txt", "r", stdin);
    //freopen("b.txt", "w", stdout);
    #endif // LOCAL
    //´ò±í
    memset(sum, 0, sizeof sum);
    memset(ans, 0, sizeof ans);
    for(unsLL i = 0; i < maxn; i++){
        if(i != 0) sum[i] = sum[i - 1] + i;
        else sum[i] = 0;
    }
    sum[1] = 0;
    for(unsLL i = 2; i < maxn; i++){
        sum[i] -= i;
        for(unsLL j = 2; j * i < maxn; j++){
            if(i * j < maxn)sum[i * j] -= sum[i] * j;  //!j * i < maxn, 然后j++, 这个时候可能 i * j 已经 >= maxn了
        }
    }
    //cout<<"here"<<endl;
    ans[1] = 0;
    for(unsLL i = 2; i < maxn; i++){
        ans[i] += ans[i-1];
        for(unsLL j = 1; j * i < maxn; j++){
            if(i * j < maxn) ans[i * j] += sum[i] * i * j;//! 同上
        }
    }
    //cout<<"here"<<endl;

    int T, n, kase = 0;
    scanf("%d", &T);
    while(T--){
        scanf("%d", &n);
        printf("Case %d: %llun", ++kase, ans[n]);
    }
    return 0;
}

非特殊说明，本博所有文章均为博主原创，未经许可不得转载。

https://www.prolightsfxjh.com/

Thank you!

                                                                                                                                             ------from ProLightsfx