3944: Sum

贴模板

总结见学习笔记(现在还没写23333)

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

typedef long long ll;

#define pii pair<ll, ll>

#define fir first

#define sec second

const int N=1664512, U=1664510;

inline ll read(){

	char c=getchar(); ll x=0,f=1;

	while(c<'0' || c>'9') {if(c=='-')f=-1; c=getchar();}

	while(c>='0' && c<='9') {x=x*10+c-'0'; c=getchar();}

	return x*f;

}

bool notp[N]; int p[N/10], mu[N]; ll phi[N];

void sieve(int n) {

	mu[1] = phi[1] = 1;

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

		if(!notp[i]) p[++p[0]] = i, mu[i] = -1, phi[i] = i-1;

		for(int j=1; j <= p[0] && i*p[j] <= n; j++) {

			int t = i*p[j];

			notp[t] = 1;

			if(i % p[j] == 0) {mu[t] = 0; phi[t] = phi[i]*p[j]; break;}

			mu[t] = -mu[i]; phi[t] = phi[i]*(p[j]-1);

		}

		mu[i] += mu[i-1]; phi[i] += phi[i-1];

	}

}

ll n;

pii nul(-1, -1);

namespace ha {

	const int p = 1001001;

	struct meow{int ne; pii val; ll r;} e[30000];

	int cnt=1, h[p];

	inline void insert(ll x, pii &val) {

		ll u = x % p;

		for(int i=h[u];i;i=e[i].ne) if(e[i].r == x) return;

		e[++cnt] = (meow){h[u], val, x}; h[u]=cnt;

	}

	inline pii quer(ll x) {

		ll u = x % p;

		for(int i=h[u];i;i=e[i].ne) if(e[i].r == x) return e[i].val;

		return nul;

	}

} using ha::insert; using ha::quer;

pii dj_sieve(ll n) {

	if(n <= U) return make_pair(mu[n], phi[n]);

	if(quer(n) != nul) return quer(n);

	pii ans(1, n*(n+1)/2); ll r;

	for(ll i=2; i<=n; i=r+1) {

		r = n/(n/i);

		pii t = dj_sieve(n/i);

		ans = make_pair(ans.fir - t.fir * (r-i+1), ans.sec - t.sec * (r-i+1));

	}

	insert(n, ans);

	return ans;

}

int main() {

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

	sieve(U);

	int T=read();

	while(T--) {

		n=read(); if(n==0) {puts("0 0"); continue;}

		pii t = dj_sieve(n);

		printf("%lld %lld\n", t.sec, t.fir);

	}

}