【BZOJ 3944】Sum

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3944

好像没有什么特别的
但讲道理,下面是map,上面是unordered_map
979547587
讲道理啊!这™复杂度都不一样啊!
HP@{Q%Y1HMU{H9M4V]{N6)D

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 5000000+9;
const int MX = 5000000; 

int mu[N],cnt,pri[N];
bool vis[N]; LL phi[N];
map<int,int> MU;
map<int,LL> PHI;

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

inline void prework(){
	mu[1] = phi[1] = 1;
	for (int i=2;i<=MX;i++) {
		if (!vis[i]) pri[++cnt] = i, mu[i] = -1, phi[i] = i-1;
		for (int j=1,w;j<=cnt && pri[j]*i<=MX;j++) {
			vis[i*pri[j]] = 1; w = pri[j]*i;
			if (i%pri[j]) mu[w] = -mu[i], phi[w] = phi[i]*(pri[j]-1);
			else {phi[w] = phi[i]*pri[j]; break;}
		}
	} 
	for (int i=1;i<=MX;i++) mu[i] += mu[i-1], phi[i] += phi[i-1];
}

inline int solve_mu(int w) {
	if (w <= MX) return mu[w];
	else if (MU[w]) return MU[w];
	else {
		int ret = 1;
		for (LL i=2,tmp;i<=w;i=tmp+1) {
			tmp = w / (w / i);
			ret -= solve_mu(w/tmp)*(tmp-i+1);
		} MU[w] = ret; return ret;
	}
}

int LL solve_phi(int w) {
    if (w <= MX) return phi[w];
    else if (PHI[w]) return PHI[w];
    else {
        LL ret = w * ((LL)w+1) / 2;
        for (LL i=2,tmp;i<=w;i=tmp+1) {
            tmp = w / (w/i); 
            ret -= solve_phi(w/tmp)*(tmp-i+1);
        } PHI[w] = ret; return ret;
    } 
}

int main(){
	prework(); 
	for (int t=read(),w;t;t--) w = read(), 
		printf("%lld %d\n",solve_phi(w),solve_mu(w));
	return 0;
}

16 thoughts to “【BZOJ 3944】Sum”

  1. 834930 286304This really is a proper weblog for would like to discover out about this subject. You realize a lot its almost challenging to argue along (not that I personally would wantHaHa). You in fact put the latest spin with a subject thats been discussed for a long time. Amazing stuff, just great! 879992

  2. 334018 363245Speedily and easily build your internet traffic and PR, which provides Internet site visitors to add your page to any social bookmarking internet site. 621569

  3. 498472 126188Wonderful beat ! I wish to apprentice although you amend your internet site, how can i subscribe for a blog website? The account aided me a appropriate deal. I had been a little bit acquainted of this your broadcast provided bright clear concept 329617

  4. 363204 291755Id need to talk to you here. Which is not some thing Which i do! I like reading an write-up that can make men and women believe. Also, thank you for permitting me to comment! 362421

  5. 505698 168539The when I just read a blog, Im hoping that this doesnt disappoint me approximately this one. Get real, Yes, it was my method to read, but When i thought youd have something intriguing to state. All I hear is really a number of whining about something which you could fix should you werent too busy trying to discover attention. 481095

  6. I haven?¦t checked in here for some time as I thought it was getting boring, but the last few posts are good quality so I guess I will add you back to my everyday bloglist. You deserve it my friend 🙂

Leave a Reply

Your email address will not be published. Required fields are marked *