# 桃園高中第一次資訊讀書會
資訊讀書會?講一下可能跟競程有關(或無關)的東東。
~~(如果有寫錯噴小力一點，但我猜應該沒人看)~~
****
# 時間複雜度

1. Big-O( Ο )：演算法時間函式的上限(Upper bound)
1. Omega( Ω )：演算法時間函式的下限(Lower bound)
1. Theta( θ )：演算法時間函式的上限與下限

先簡單介紹Big-O，他的嚴格定義是，找到一個n0與c使得
f(n)<=O(c*n)在(n>=n0)的情況下，舉例:f(n)=3n^2他就屬於

學者發表在期刊上的演算法，通常是找到更加優化的解，例如O(n^2)變成 O(nlogn)，或是找到新的資料結構能優化演算法，例如binary indexed tree。

# p與np

先介紹指數時間跟多項式時間

1. 指數時間:問題求解所花的步驟，會隨著n的輸入規模成指數成長。例如:T(n)= 2^n(n每多1，步驟就要多兩倍)
3. 多項式時間:能夠表示成多項式，例如:T(n)=n^3+ 2n^2+n-7

指數時間遠遠多於多項式時間
你一定能夠找到一個n，使得指數時間遠遠大於多項式時間，這是必然的。

2^n 屬於非多項式時間。 n^k 是多項式時間。

# 大數問題
***假設問題***

真實世界的問題都挺複雜的，我們先從簡單的情況考慮問題。

1. 如果我們只是想要在一台計算機加減乘除，多餘的位數要怎麼處理?(假設計算機最大顯示位數是9-10位)
2. 如果除法要求求出他的循環小數要怎麼做?


大數加法
15000000+15000000=30000000，這很簡單，~~小學生都會寫程式算~~。

但如果是10^30+ 10^30 超出 int or long long 範圍的怎麼辦?

~~int128~~

_int128 read() {
    __int128 x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (c >= '0' && ch <= '9') {
        x = x * 10 + ch - '0';
        ch = getchar();
    }
    return x * f;
}
void print(__int128 x) {
    if (x < 0) {
        putchar('-');
        x = -x;
    }
    if (x > 9) print(x / 10);
    putchar(x % 10 + '0');
}
bool cmp(__int128 x, __int128 y) { return x > y; }

程式碼來源:https://codeforces.com/blog/entry/75044#:~:text=As%20an%20extension%20the%20integer,an%20unsigned%20128%2Dbit%20integer.

~~建議不要亂用~~~~畢竟他最大也只能存(2^127)-1 ~ (-2^127)

**正題:**

怎麼寫大數加法?

int 只能存(10^9) ，long long 只能存(10^18)，我們觀察一下這個數字 184639257

觀察後發現可以拆成 9 個 int，什麼東西可以存很多個數字或字元?

:::spoiler [hint]

陣列

:::

*******

還有一個問題要解決，直接把大數當int or long long 輸入會溢位，要怎麼處理?

:::spoiler [hint2]

字元或字串

:::

//輸入兩個大數自動相加，格式: 100 200 輸出:300
#include<bits/stdc++.h>
using namespace std;

int a[10005],b[10005],c[10005];
int main(){
	
	string n,m;
	
	cin>>n>>m;
	reverse(n.begin(),n.end());//翻轉相反頭尾
	reverse(m.begin(),m.end());
	
	for(int i=0;i<=n.size()-1;i++){
		a[10000-i]=n[i]-'0';
		
	}
	
	for(int i=0;i<=m.size()-1;i++){
		b[10000-i]=m[i]-'0';
	}
	//for(int i=9980;i<=10000;i++) cout<<a[i];
	//for(int i=9980;i<=10000;i++) cout<<b[i];
	
	
	for(int i=10000;i>0;i--){
		c[i]=c[i]+a[i]+b[i];
		if(c[i]>=10) c[i-1]++;
		c[i]%=10;
	}
	int ans = 0;
	for(int i=1;i<=10000;i++){
		if(c[i]!=0) {
			ans=i;
			break;
		}
	}
	if(!ans) cout<<0<<'\n';
	for(int i=ans;i<=10000;i++){
		cout<<c[i];
	}
}//超級偷懶，空間開太大了

時間複雜度為O(n)

還有一個問題，我們能繼續優化他嗎???

幾個方向
1. 如果我們知道我們要算幾位數+幾位數?
2. 我們可以分塊分成17|17|17 開三個long long ?

時間複雜度是?

****
**大數減法**

easy，但細節要討論，怎麼借位?
10-5是很簡單的借位，但100-5? 1000-5? 10000-5?

還有什麼細節需要討論的?如果第一個數小於第二個數呢?

之後補

****
大數乘法

怎麼乘?如果有小數點怎麼辦呢?
或是兩個都小於1，但大於0怎麼辦呢?
時間複雜度?

****
大數除法

****
~~先把我婆放上去~~~~~~