注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

n+e

NewWeb:http://trinkle.is-programmer.com/

 
 
 

日志

 
 

[BZOJ3944]Sum  

2015-06-26 22:06:46|  分类: BZOJ |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

3944: Sum

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 570  Solved: 137
[Submit][Status][Discuss]

Description

Input

一共T+1行
第1行为数据组数T(T<=10)
第2~T+1行每行一个正整数N,代表一组询问

Output

一共T行,每行两个用空格分隔的数ans1,ans2

Sample Input

6 1 2 8 13 30 2333

Sample Output

1 1 2 0 22 -2 58 -3 278 -3 1655470 2

Solution

[BZOJ3944]Sum - Trinkle - n+e
以上转自Gromah 
 然而网络上的题解都没有证明复杂度。。。
[BZOJ3944]Sum - Trinkle - n+e

Code

/**************************************************************
    Problem: 3944
    User: wjy1998
    Language: C++
    Result: Accepted
    Time:6604 ms
    Memory:109360 kb
****************************************************************/
 
#include<cstdio>
#include<cmath>
#define rg register
typedef long long ll;
typedef unsigned U;
const ll oo=1LL<<60;
#define N 1<<22
const int M=(1<<18)-1;
int n,k,p[N],t,vis[N],T,a[20];ll phi[N],miu[N];
class map{public:
    int et,la[M+1];
    struct E{int nxt;U x;ll ans;}e[1<<18];
    inline ll find(rg U x){
        for(rg int i=la[x&M];i;i=e[i].nxt)
        if(e[i].x==x)return e[i].ans;
        return -oo;
    }
    inline void ins(rg U x,rg ll ans){
        e[++et]=(E){la[x&M],x,ans},la[x&M]=et;
    }
}_phi,_miu;
ll getphi(rg U n){
    if(n<=k)return phi[n];
    rg ll ans=_phi.find(n);
    if(ans!=-oo)return ans;ans=n*(n+1LL)/2;
    for(rg U l=2,r;l<=n;l=r+1)r=n/(n/l),ans-=(r-l+1)*getphi(n/l);
    return _phi.ins(n,ans),ans;
}
ll getmiu(rg U n){
    if(n<=k)return miu[n];
    rg ll ans=_miu.find(n);
    if(ans!=-oo)return ans;ans=1;
    for(rg U l=2,r;l<=n;l=r+1)r=n/(n/l),ans-=(r-l+1)*getmiu(n/l);
    return _miu.ins(n,ans),ans;
}
int main(){
    scanf("%d",&T);
    for(int i=1;i<=T;i++)scanf("%d",a+i),n<a[i]?n=a[i]:1;
    k=2.5*pow(n,2.0/3)+1;phi[1]=miu[1]=1;
    for(rg int i=2;i<=k;i++){
        if(!vis[i])p[++t]=i,phi[i]=i-1,miu[i]=-1;
        for(rg int j=1;j<=t&&i*p[j]<=k;j++){
            vis[i*p[j]]=1;
            if(i%p[j]==0){
                phi[i*p[j]]=phi[i]*p[j];
                break;
            }
            phi[i*p[j]]=phi[i]*phi[p[j]],miu[i*p[j]]=-miu[i];
        }
    }
    for(rg int i=2;i<=k;i++)phi[i]+=phi[i-1],miu[i]+=miu[i-1];
    for(int i=1;i<=T;i++)printf("%lld %lld\n",getphi(a[i]),getmiu(a[i]));
}

  评论这张
 
阅读(507)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018