网站后台管理系统制作软件,深圳发型网站建设,大型网站开发心得,做素材网站服务器正题
题目链接:https://www.luogu.com.cn/problem/P4213 题目大意
给出nnn#xff0c;求∑i1nφ(i)\sum_{i1}^n\varphi(i)i1∑nφ(i) 和 ∑i1nμ(i)\sum_{i1}^n\mu(i)i1∑nμ(i) 解题思路
考虑如何将φ\varphiφ卷起来#xff0c;我们可以乘上一个函数I(I(x)1)I(I(x)1…正题
题目链接:https://www.luogu.com.cn/problem/P4213 题目大意
给出nnn求∑i1nφ(i)\sum_{i1}^n\varphi(i)i1∑nφ(i) 和 ∑i1nμ(i)\sum_{i1}^n\mu(i)i1∑nμ(i) 解题思路
考虑如何将φ\varphiφ卷起来我们可以乘上一个函数I(I(x)1)I(I(x)1)I(I(x)1)就有 (φ∗I)(n)∑d∣nφ(d)I(nd)(\varphi*I)(n)\sum_{d|n}\varphi(d)I(\frac{n}{d})(φ∗I)(n)∑d∣nφ(d)I(dn) 变成杜教筛的式子之后就是 I(1)S(n)∑i1n(φ∗I)(n)−∑i2nI(i)∗S(⌊ni⌋)I(1)S(n)\sum_{i1}^n(\varphi*I)(n)-\sum_{i2}^nI(i)*S(\lfloor \frac{n}{i}\rfloor)I(1)S(n)i1∑n(φ∗I)(n)−i2∑nI(i)∗S(⌊in⌋)
整除分块计算下去就好了。
μ\muμ同理 codecodecode
#includecstdio
#includecstring
#includealgorithm
#includemap
#define ll long long
using namespace std;
const ll N1e71;
ll T,n,cnt,mu[N],phi[N],pri[N];
bool vis[N];
mapll,ll sp,sm;
void prime(){mu[1]phi[1]1;for(ll i2;iN;i){if(!vis[i])pri[cnt]i,mu[i]-1,phi[i]i-1;for(ll j1;jcntpri[j]*iN;j){vis[pri[j]*i]1;if(i%pri[j]0){phi[i*pri[j]]phi[i]*pri[j];break;}phi[i*pri[j]]phi[pri[j]]*phi[i];mu[i*pri[j]]-mu[i];}}for(ll i1;iN;i)phi[i]phi[i-1],mu[i]mu[i-1];return;
}
ll GetSphi(ll n){if(nN)return phi[n];if(sp[n])return sp[n];ll restn*(n1ll)/2ll;for(ll l2ll,r;ln;lr1ll)rn/(n/l),rest-(r-l1ll)*GetSphi(n/l);return (sp[n]rest);
}
ll GetSmul(ll n){if(nN)return mu[n];if(sm[n])return sm[n];ll rest1ll;for(ll l2ll,r;ln;lr1ll)rn/(n/l),rest-(r-l1ll)*GetSmul(n/l);return (sm[n]rest);
}
int main()
{scanf(%lld,T);prime();while(T--){scanf(%lld,n);printf(%lld %lld\n,GetSphi(n),GetSmul(n));}
}
