天梯练习——数列求和-加强版（数学思维）

悠悠 2022-12-21 06:08 141阅读 0赞

### 数列求和 ###

![题目][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center]

--------------------

两种方法：大数相加、位运算。

#### 大数相加 ####

这个相对比较暴力，单纯的枚举相加，在 N 取较大的时候会超时，复杂度估计要 O(N2)以上。

//暴力法 
    #include<bits/stdc++.h>
    using namespace std;
    int s[100010], now[100010];
    int n, h;
    
    void add(int tmp){ 
    	int d=0;
    	int c = max(h, tmp);
    	for(int i=0; i<=c; i++){ 
    		s[i] = s[i]+now[i]+d;
    		d = s[i]/10;
    		s[i] = s[i]%10;
    	}
    	if(d!=0)
    		s[++c] = d;
    	h=c;
    	return;
    }
    
    int main(){ 
    	int tmp;
    	scanf("%d%d", &tmp, &n);
    	memset(now, 0, sizeof(now));
    	memset(s, 0, sizeof(s));
    	
    	h=0;    
    	for(int i=0; i<n; i++){ 
    		now[i] = tmp;
    		add(i);
    	}
    	for(int i=h; i>=0; i--)
    		printf("%d", s[i]);
    	printf("\n");
    	return 0;
    }

--------------------

#### 位运算 ####

单独对每个位进行计算，有进位则进位，复杂度为O(N)。  
例如 A=8，N=4

#include<bits/stdc++.h>
    using namespace std;
    int w[100010], ans[100010];
    int main(){ 
    	int tmp, n, i, d=0;
    	scanf("%d%d", &tmp, &n);
    	memset(ans, 0, sizeof(ans));
    	for(i=0; i<n||d!=0; i++){ 
    		ans[i] += d + (n-i)*tmp;
    		d = ans[i]/10;
    		ans[i] %= 10;
    	}
    	
    	for(i>0?i--:i=0; i>=0; i--)
    		printf("%d", ans[i]);
    	printf("\n");
    	
    	return 0;
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L1poZW5neWFuZ3hpbm4_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/be736298362d40e3b8e1486fec43bacb.png