A simple Blog for wyx I've been down the bottle hoping.
BZOJ 2226 sum of lcm 数论
发表于: | 分类: Oi | 评论:0 | 阅读:42

题目大意:给定n,求$LCM(1,n)+LCM(2,n)+...+LCM(n,n)$

枚举$d=(i,n)$,

令F(n)为n以内与n互质的数之和
则$ans=\sum\limits_{d|n}\frac{d\times F(d)\times n}{d} =n\sum F(d)$

现在就是$F(n)$的问题了 我们发现对于任意$3\le n$,如果$(x,n) = 1 $,

那么通过更相减损可以知道$(n-x,n)=1$
故$n$以内与$n$互质的数能两两凑成和为$n$的数对,一共$\frac{\phi(n)}{2}$对,故$F(n)=\frac{n*\phi(n)}{2}$

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1e6+5;
const int Max = 1e6;
typedef long long LL;
int phi[N],prime[N],cnt;
bool F[N];

void init() {
    register int j; int i;
    phi[1] = 1;
    for(i=2;i<=Max;++i) {
        if(!F[i]) prime[++cnt] = i, phi[i] = i - 1;
        for(j=1;prime[j]*i<=Max;++j) {
            F[prime[j]*i] = 1;
            if(i % prime[j] == 0) {
                phi[i*prime[j]] = phi[i] * prime[j];
                break;
            }       
            phi[prime[j]*i] = phi[i] * (prime[j]-1);
        }
    }
}

inline LL calc(int x) {
    if(x == 1)  return 1ll;
    return (LL) x * phi[x] >> 1;
}

LL solve(int x) {
    int i; LL ans = 0;
    for(i=1;i*i<x;++i)  if(x%i==0) ans += calc(i), ans += calc(x/i);
    if(i*i==x) ans += calc(i); return ans;
}

inline int read() {
    int x=0,f=1;char ch = getchar();
    while(ch < '0' || ch > '9'){if(ch == '-')f=-1;ch = getchar();}
    while(ch >='0' && ch <='9'){x=(x<<1)+(x<<3)+ch-'0';ch = getchar();}
    return x*f;
}

int main() {
    int n, q = read(); init();
    while(q--) {
        n = read();
        printf("%lld\n",solve(n)*n);
    }
}
Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP