laekov

BZOJ2226 LCMSum

比较神奇的数学题。


重要的结论是<n且与n素质的数的和是phi(n)*n/2。


所以就枚举一下gcd就好了。


#include <cstdio>

#include <cctype>

#include <memory.h>

#include <algorithm>


using namespace std;


typedef long long qw;


#ifdef WIN32

#define lld "%I64d"

#else

#define lld "%lld"

#endif

#define _l (qw)

#define readInt(_s_) {\

int _d_;\

_s_ = 0;\

while (!isdigit(_d_ = getchar()));\

while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar()));\

}


const int maxn = 1000009;


qw ans[maxn];

int tp, pn[maxn], phi[maxn];

bool pr[maxn];


void pre() {

memset(pr, 0, sizeof(pr));

tp = 0;

phi[1] = 1;

for (int i = 2; i < maxn; ++ i) {

if (!pr[i]) {

pn[tp ++] = i;

phi[i] = i - 1;

}

for (int j = 0; j < tp && i * pn[j] < maxn; ++ j) {

pr[i * pn[j]] = 1;

if (i % pn[j])

phi[i * pn[j]] = phi[i] * phi[pn[j]];

else {

phi[i * pn[j]] = phi[i] * pn[j];

break;

}

}

}

memset(ans, 0, sizeof(ans));

for (int i = 1; i < maxn; ++ i) {

for (int j = 2; j * i < maxn; ++ j)

ans[i * j] += _l i * j * j * phi[j] / 2;

}

for (int i = 1; i < maxn; ++ i)

ans[i] += i;

}


int main() {

#ifndef ONLINE_JUDGE

freopen("in.txt", "r", stdin);

#endif


pre();

int t;

readInt(t);

while (t --) {

int x;

readInt(x);

printf(lld "\n", ans[x]);

}

}


评论

© laekov | Powered by LOFTER