1 条题解

  • 1
    @ 2026-9-23 19:28:35

    真签到题

    给它每一项全写出来可以发现一个规律,从第二项开始

    a2=a1−1,a3=a1+1,a4=a2+1,a5=a2−1......a_2=a_1-1,a_3=a_1+1,a_4=a2+1,a_5=a2-1......

    可以发现 ∑i=1nai=2∗∑i=1n/2ai\sum_{i=1}^{n}a_i=2*\sum_{i=1}^{n/2}a_i

    当n为偶数的话将最后一个特殊算出来就行了

    时间复杂度O(lognlogn)

    #include<stdio.h>
    int main(){
    	long long n,sum=0,a[4]={0,0,-1},c[5]={1,-1,-1,1},cnt=1;
    	scanf("%lld",&n);
    	while(n>2){
    		if(!(n%2)){
    			long long d=n,x=0;
    			while(d>=2){
    				x+=c[d%4];
    				d/=2;
    			}
    			sum+=cnt*(x+a[d]);
    			n-=1;
    		}
    		n/=2;
    		cnt*=2;
    	}
    	sum+=a[n]*cnt;
    	printf("%lld",sum);
    }
    
    • 1

    信息

    ID
    2348
    时间
    1000ms
    内存
    256MiB
    难度
    2
    标签
    递交数
    105
    已通过
    2
    上传者