- #include<bits/stdc++.h>
- #include<tr1/unordered_map>
- #define fi first
- #define se second
- #define INF 0x3f3f3f3f
- #define fio iOS::sync_with_stdio(false);cin.tie(0);cout.tie(0)
- #define pqueue priority_queue
- #define NEW(a,b) memset(a,b,sizeof(a))
- #define lowbit(x) (x&(-x))
- #define si(x) scanf("%d",&x)
- #define sl(x) scanf("%lld",&x)
- #define lc (d<<1)
- #define rc (d<<1|1)
- const double pi=4.0*atan(1.0);
- const double e=exp(1.0);
- const int maxn=6e6+8;
- typedef long long LL;
- typedef unsigned long long ULL;
- const LL mod=1e6+3;
- const ULL base=1e7+7;
- using namespace std;
- bool vis[maxn];
- int mu[maxn],sum1[maxn],phi[maxn];
- LL sum2[maxn];
- int cnt,prim[maxn];
- tr1::unordered_map<LL,LL>w1;
- tr1::unordered_map<int,int>w;
- void get(int N){
- phi[1]=mu[1]=1;
- for(int i=2;i<=N;i++){
- if(!vis[i]){
- prim[++cnt]=i;
- mu[i]=-1;phi[i]=i-1;
- }
- for(int j=1;j<=cnt&&prim[j]*i<=N;j++){
- vis[i*prim[j]]=1;
- if(i%prim[j]==0){
- phi[i*prim[j]]=phi[i]*prim[j];
- break;
- }
- else mu[i*prim[j]]=-mu[i],phi[i*prim[j]]=phi[i]*(prim[j]-1);
- }
- }
- for(int i=1;i<=N;i++)sum1[i]=sum1[i-1]+mu[i],sum2[i]=sum2[i-1]+phi[i];
- }
- int djsmu(int x){
- if(x<=6000000)return sum1[x];
- if(w.count(x))return w[x];
- int ans=1;
- for(int l=2,r;l<=x;l=r+1){
- r=x/(x/l);
- ans-=(r-l+1)*djsmu(x/l);
- }
- return w[x]=ans;
- }
- LL djsphi(LL x){
- if(x<=6000000)return sum2[x];
- if(w1.count(x))return w1[x];
- LL ans=x*(x+1)/2;
- for(LL l=2,r;l<=x;l=r+1){
- r=x/(x/l);
- ans-=(r-l+1)*djsphi(x/l);
- }
- return w1[x]=ans;
- }
- int main(){
- cin.tie(0);
- cout.tie(0);
- int T;
- cin>>T;
- get(6000000);
- int x;
- while(T--){
- scanf("%d",&x);
- printf("%lld %d\n",djsphi(x),djsmu(x));
- }
- }
杜教筛
来源: http://www.bubuko.com/infodetail-3119209.html