Andrew Stankevich's Contest (1)

Andrew Stankevich's Contest (1)

打一半出门了，回来才补完了。。。各种大数又不能上java。。也是蛋疼无比

A：依据置换循环节非常easy得出要gcd(x, n) = 1而且x <= n / 2，那么把相应几种情况的最大值考虑一下就可以，各自是n % 2 = 1为n / 2, n % 4 = 0为n / 2 - 1，n % 4 = 2为n / 2 - 2

B：限制下限的最大流，建模方法为原来容量变成c - l，然后源点连到每一个点的下限和为正，每一个点下限和为负连到汇点，跑一下最大流，假设源点流出的所有满流就是有解，然后输出的时候仅仅要把相应的自由流加上下限就可以

C：贪心，从叶子结点不断往上推，一有合适就用掉，然后把父结点标记一下用来推断就可以

D：就简单的矩阵相乘，因为要考虑复杂度，所以能够先算出没排的和，然后每一个位置分别乘上相应那排再累加就可以

E：矩阵高速幂，把两两关系确立后，建立矩阵跑一下高速幂就可以

F：几何题，推断有限视角和是否会形成-2pi，利用spfa判负环就可以

G：LIS，先按x从小到大，再按y从大到小排序，这样对y做lis就是答案，因为要输出路径，所以开一个dp数组记录下每一个位置的答案，然后在扫一遍随意输出一种方案就可以

H：高斯消元，和大白书上例题差点儿相同，全然平方数的每一个因子必定是偶数，这样就能够建立异或方程，然后计算出自由便元个数x，那么答案就是2^x - 1

代码：

A:

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

typedef long long ll;

const int MAXN = 2005;

struct bign {

    int len;

    ll num[MAXN];

    bign () {

        len = 0;

        memset(num, 0, sizeof(num));

    }

    bign (ll number) {*this = number;}

    bign (const char* number) {*this = number;}

    void DelZero ();

    void Put ();

    void operator = (ll number);

    void operator = (char* number);

    bool operator <  (const bign& b) const;

    bool operator >  (const bign& b) const { return b < *this; }

    bool operator <= (const bign& b) const { return !(b < *this); }

    bool operator >= (const bign& b) const { return !(*this < b); }

    bool operator != (const bign& b) const { return b < *this || *this < b;}

    bool operator == (const bign& b) const { return !(b != *this); }

    void operator ++ ();

    void operator -- ();

    bign operator + (const int& b);

    bign operator + (const bign& b);

    bign operator - (const int& b);

    bign operator - (const bign& b);

    bign operator * (const ll& b);

    bign operator * (const bign& b);

    bign operator / (const ll& b);

    //bign operator / (const bign& b);

    int operator % (const int& b);

};

/*Code*/

char str[2005];

int main() {

    while (~scanf("%s", str)) {

        bign sb;

        sb = str;

        bign ans;

        if (sb % 2) ans = sb / 2;

        else if (sb % 4 == 0) ans = sb / 2 - 1;

        else ans = sb / 2 - 2;

        ans.Put();

        printf("\n");

    }

    return 0;

}

/*********************************************/

void bign::DelZero () {

    while (len && num[len-1] == 0)

        len--;

    if (len == 0) {

        num[len++] = 0;

    }

}

void bign::Put () {

    for (int i = len-1; i >= 0; i--)

        printf("%lld", num[i]);

}

void bign::operator = (char* number) {

    len = strlen (number);

    for (int i = 0; i < len; i++)

        num[i] = number[len-i-1] - '0';

    DelZero ();

}

void bign::operator = (ll number) {

    len = 0;

    while (number) {

        num[len++] = number%10;

        number /= 10;

    }

    DelZero ();

}

bool bign::operator < (const bign& b) const {

    if (len != b.len)

        return len < b.len;

    for (int i = len-1; i >= 0; i--)

        if (num[i] != b.num[i])

            return num[i] < b.num[i];

    return false;

}

void bign::operator ++ () {

    int s = 1;

    for (int i = 0; i < len; i++) {

        s = s + num[i];

        num[i] = s % 10;

        s /= 10;

        if (!s) break;

    }

    while (s) {

        num[len++] = s%10;

        s /= 10;

    }

}

void bign::operator -- () {

    if (num[0] == 0 && len == 1) return;

    int s = -1;

    for (int i = 0; i < len; i++) {

        s = s + num[i];

        num[i] = (s + 10) % 10;

        if (s >= 0) break;

    }

    DelZero ();

}

bign bign::operator + (const int& b) {

    bign a = b;

    return *this + a;

}

bign bign::operator + (const bign& b) {

    int bignSum = 0;

    bign ans;

    for (int i = 0; i < len || i < b.len; i++) {

        if (i < len) bignSum += num[i];

        if (i < b.len) bignSum += b.num[i];

        ans.num[ans.len++] = bignSum % 10;

        bignSum /= 10;

    }

    while (bignSum) {

        ans.num[ans.len++] = bignSum % 10;

        bignSum /= 10;

    }

    return ans;

}

bign bign::operator - (const int& b) {

    bign a = b;

    return *this - a;

}

bign bign::operator - (const bign& b) {

    ll bignSub = 0;

    bign ans;

    for (int i = 0; i < len || i < b.len; i++) {

        bignSub += num[i];

        if (i < b.len)

            bignSub -= b.num[i];

        ans.num[ans.len++] = (bignSub + 10) % 10;

        if (bignSub < 0) bignSub = -1;

        else bignSub = 0;

    }

    ans.DelZero();

    return ans;

}

bign bign::operator * (const ll& b) {

    ll bignSum = 0;

    bign ans;

    ans.len = len;

    for (int i = 0; i < len; i++) {

        bignSum += num[i] * b;

        ans.num[i] = bignSum % 10;

        bignSum /= 10;

    }

    while (bignSum) {

        ans.num[ans.len++] = bignSum % 10;

        bignSum /= 10;

    }

    return ans;

}

bign bign::operator * (const bign& b) {

    bign ans;

    ans.len = 0;

    for (int i = 0; i < len; i++){

        int bignSum = 0;

        for (int j = 0; j < b.len; j++){

            bignSum += num[i] * b.num[j] + ans.num[i+j];

            ans.num[i+j] = bignSum % 10;

            bignSum /= 10;

        }

        ans.len = i + b.len;

        while (bignSum){

            ans.num[ans.len++] = bignSum % 10;

            bignSum /= 10;

        }

    }

    return ans;

}

bign bign::operator / (const ll& b) {

    bign ans;

    ll s = 0;

    for (int i = len-1; i >= 0; i--) {

        s = s * 10 + num[i];

        ans.num[i] = s/b;

        s %= b;

    }

    ans.len = len;

    ans.DelZero();

    return ans;

}

int bign::operator % (const int& b) {

    bign ans;

    int s = 0;

    for (int i = len-1; i >= 0; i--) {

        s = s * 10 + num[i];

        ans.num[i] = s/b;

        s %= b;

    }

    return s;

}

B:

#include <cstdio>

#include <cstring>

#include <queue>

#include <algorithm>

using namespace std;

const int MAXNODE = 205;

const int MAXEDGE = 210005;

typedef int Type;

const Type INF = 0x3f3f3f3f;

struct Edge {

	int u, v;

	Type cap, flow, low;

	Edge() {}

	Edge(int u, int v, Type cap, Type flow, Type low) {

		this->u = u;

		this->v = v;

		this->cap = cap;

		this->flow = flow;

		this->low = low;

	}

};

struct Dinic {

	int n, m, s, t;

	Edge edges[MAXEDGE];

	int first[MAXNODE];

	int next[MAXEDGE];

	bool vis[MAXNODE];

	Type d[MAXNODE];

	int cur[MAXNODE];

	vector<int> cut;

	void init(int n) {

		this->n = n;

		memset(first, -1, sizeof(first));

		m = 0;

	}

	void add_Edge(int u, int v, Type cap, Type low) {

		edges[m] = Edge(u, v, cap, 0, low);

		next[m] = first[u];

		first[u] = m++;

		edges[m] = Edge(v, u, 0, 0, low);

		next[m] = first[v];

		first[v] = m++;

	}

	bool bfs() {

		memset(vis, false, sizeof(vis));

		queue<int> Q;

		Q.push(s);

		d[s] = 0;

		vis[s] = true;

		while (!Q.empty()) {

			int u = Q.front(); Q.pop();

			for (int i = first[u]; i != -1; i = next[i]) {

				Edge& e = edges[i];

				if (!vis[e.v] && e.cap > e.flow) {

					vis[e.v] = true;

					d[e.v] = d[u] + 1;

					Q.push(e.v);

				}

			}

		}

		return vis[t];

	}

	Type dfs(int u, Type a) {

		if (u == t || a == 0) return a;

		Type flow = 0, f;

		for (int &i = cur[u]; i != -1; i = next[i]) {

			Edge& e = edges[i];

			if (d[u] + 1 == d[e.v] && (f = dfs(e.v, min(a, e.cap - e.flow))) > 0) {

				e.flow += f;

				edges[i^1].flow -= f;

				flow += f;

				a -= f;

				if (a == 0) break;

			}

		}

		return flow;

	}

	Type Maxflow(int s, int t) {

		this->s = s; this->t = t;

		Type flow = 0;

		while (bfs()) {

			for (int i = 0; i < n; i++)

				cur[i] = first[i];

			flow += dfs(s, INF);

		}

		return flow;

	}

	bool solve(int s, int t, int tot) {

		Maxflow(s, t);

		for (int i = first[s]; i + 1; i = next[i]) {

			if (edges[i].flow != edges[i].cap) return false;

		}

		printf("YES\n");

		for (int i = 0; i < 2 * tot; i += 2)

			printf("%d\n", edges[i].flow + edges[i].low);

		return true;

	}

	void MinCut() {

		cut.clear();

		for (int i = 0; i < m; i += 2) {

			if (vis[edges[i].u] && !vis[edges[i].v])

				cut.push_back(i);

		}

	}

} gao;

const int N = 205;

int n, m, M[N];

int main() {

	while (~scanf("%d%d", &n, &m)) {

		gao.init(n + 2);

		int u, v, l, c;

		memset(M, 0, sizeof(M));

		for (int i = 0; i < m; i++) {

			scanf("%d%d%d%d", &u, &v, &l, &c);

			gao.add_Edge(u, v, c - l, l);

			M[u] -= l;

			M[v] += l;

		}

		for (int i = 1; i <= n; i++) {

			if (M[i] > 0) gao.add_Edge(0, i, M[i], 0);

			else if (M[i] < 0) gao.add_Edge(i, n + 1, -M[i], 0);

		}

		if (!gao.solve(0, n + 1, m)) printf("NO\n");

	}

	return 0;

}

C:

#include <cstdio>

#include <cstring>

#include <queue>

#include <set>

#include <algorithm>

using namespace std;

const int N = 500005;

int n, fa[N], du[N], vis[N];

int out[N], on;

int main() {

	while (~scanf("%d", &n)) {

		int f;

		int ans = 0;

		memset(du, 0, sizeof(du));

		memset(vis, 0, sizeof(vis));

		for (int i = 2; i <= n; i++) {

			scanf("%d", &f);

			fa[i] = f;

			du[f]++;

		}

		on = 0;

		queue<int> Q;

		for (int i = 1; i <= n; i++) {

			if (du[i] == 0)

				Q.push(i);

		}

		while (!Q.empty()) {

			int u = Q.front();

			if (u == 1) break;

			Q.pop();

			if (!vis[u] && !vis[fa[u]]) {

				vis[fa[u]] = 1;

				out[on++] = u;

				ans += 1000;

			}

			du[fa[u]]--;

			if (du[fa[u]] == 0) Q.push(fa[u]);

		}

		sort(out, out + on);

		printf("%d\n", ans);

		for (int i = 0; i < on; i++)

			printf("%d%c", out[i], i == on - 1 ? '\n' : ' ');

	}

	return 0;

}

D:

#include <cstdio>

#include <cstring>

const int N = 10005;

const int M = 100005;

int n, m, cnt[N];

int u[M], v[M];

int main() {

	while (~scanf("%d%d", &n, &m)) {

		long long ans = 0;

		memset(cnt, 0, sizeof(cnt));

		for (int i = 0; i < m; i++) {

			scanf("%d%d", &u[i], &v[i]);

			cnt[u[i]]++;

			if (v[i] != u[i]) cnt[v[i]]++;

		}

		for (int i = 0; i < m; i++) {

			ans += cnt[u[i]];

			if (u[i] != v[i]) ans += cnt[v[i]];

		}

		printf("%lld\n", ans);

	}

	return 0;

}

E:

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

const ll MOD = 1000000000;

const int NUMLEN = 105;

struct Bign {

	ll num[NUMLEN];

	int len;

	void init(char *str) {

		for (int i = strlen(str) - 1; i >= 0; i--) {

			if (str[i] == '0') str[i] = '9';

			else {

				str[i]--;

				break;

			}

		}

		if (str[0] == '0') {

			int ca = strlen(str);

			for (int i = 0; i < ca; i++)

				str[i] = str[i + 1];

			str[ca - 1] = '\0';

		}

		len = 0;

		memset(num, 0, sizeof(num));

		for (int i = strlen(str) - 1; i >= 0; i -= 9) {

			for (int j = max(0, i - 8); j <= i; j++) {

				num[len] = num[len] * 10 + str[j] - '0';

			}

			len++;

		}

	}

	ll div2() {

		ll yu = 0;

		for (int i = len - 1; i >= 0; i--) {

			num[i] = num[i] + yu * MOD;

			yu = num[i] % 2;

			num[i] /= 2;

		}

		while (len > 1 && num[len - 1] == 0) len--;

		return yu;

	}

	bool iszero() {

		if (len == 1 && num[0] == 0) return true;

		return false;

	}

	void print() {

		for (int i = len - 1; i >= 0; i--) {

			if (i != len - 1) printf("%09lld", num[i]);

			else printf("%lld", num[i]);

		}

	}

} n;

const int N = 105;

char num[N];

int m, p, tot;

struct mat {

	int v[35][35];

	mat() {memset(v, 0, sizeof(v));}

	mat operator * (mat c) {

		mat ans;

		for (int k = 0; k < tot; k++) {

			for (int i = 0; i < tot; i++) {

				if (v[i][k] == 0) continue;

				for (int j = 0; j < tot; j++) {

					if (c.v[k][j] == 0) continue;

					ans.v[i][j] = (ans.v[i][j] + v[i][k] * c.v[k][j]) % p;

				}

			}

		}

		return ans;

	}

};

mat pow_mod(mat x, Bign k) {

	mat ans;

	for (int i = 0; i < tot; i++) ans.v[i][i] = 1;

	while (!k.iszero()) {

		ll sb = k.div2();

		if (sb == 1) ans = ans * x;

		x = x * x;

	}

	return ans;

}

int main() {

	while (~scanf("%s%d%d", num, &m, &p)) {

		n.init(num);

		tot = (1<<m);

		mat A;

		for (int i = 0; i < tot; i++) {

			for (int j = 0; j < tot; j++) {

				int flag = 1;

				int st = 3;

				for (int k = 0; k < m - 1; k++) {

					int sb = (i&st)>>k;

					if ((sb == 0 || sb == 3) && (i&st) == (j&st)) {

						flag = 0;

						break;

					}

					st <<= 1;

				}

				if (flag == 1) A.v[i][j] = 1;

			}

		}

		A = pow_mod(A, n);

		ll ans = 0;

		for (int i = 0; i < tot; i++) {

			for (int j = 0; j < tot; j++)

				ans = (ans + A.v[i][j]) % p;

		}

		printf("%lld\n", ans);

	}

	return 0;

}

F:

#include <cstdio>

#include <cstring>

#include <vector>

#include <cmath>

#include <algorithm>

#include <queue>

using namespace std;

typedef double Type;

const double eps = 1e-6;

const int MAXNODE = 305;

const int MAXEDGE = 100005;

struct Edge {

	int u, v;

	Type dist;

	Edge() {}

	Edge(int u, int v, Type dist) {

		this->u = u;

		this->v = v;

		this->dist = dist;

	}

};

struct BellmanFrod {

	int n, m;

	Edge edges[MAXEDGE];

	int first[MAXNODE];

	int next[MAXEDGE];

	bool inq[MAXNODE];

	Type d[MAXNODE];

	int p[MAXNODE];

	int cnt[MAXNODE];

	void init(int n) {

		this->n = n;

		memset(first, -1, sizeof(first));

		m = 0;

	}

	void add_Edge(int u, int v, Type dist) {

		edges[m] = Edge(u, v, dist);

		next[m] = first[u];

		first[u] = m++;

	}

	bool negativeCycle() {

		queue<int> Q;

		memset(inq, 0, sizeof(inq));

		memset(cnt, 0, sizeof(cnt));

		for (int i = 0; i < n; i++) {

			d[i] = 0; inq[i] = true; Q.push(i);

		}

		while (!Q.empty()) {

			int u = Q.front();

			Q.pop();

			inq[u] = false;

			for (int i = first[u]; i != -1; i = next[i]) {

				Edge& e = edges[i];

				if (d[e.v] > eps + d[u] + e.dist) {

					d[e.v] = d[u] + e.dist;

					p[e.v] = i;

					if (!inq[e.v]) {

						Q.push(e.v);

						inq[e.v] = true;

						if (++cnt[e.v] > n) return true;

					}

				}

			}

		}

		return false;

	}

} gao;

const int N = 305;

int n;

struct Circle {

	double x, y, r;

	void read() {

		scanf("%lf%lf%lf", &x, &y, &r);

	}

} c[N], cc;

double dis(Circle a, Circle b) {

	double dx = a.x - b.x;

	double dy = a.y - b.y;

	return sqrt(dx * dx + dy * dy);

}

int main() {

	while (~scanf("%d", &n)) {

		for (int i = 0; i < n; i++) c[i].read();

		cc.read();

		for (int i = 0; i < n; i++) {

			c[i].x -= cc.x;

			c[i].y -= cc.y;

			c[i].r += cc.r;

		}

		cc.x = cc.y = 0;

		gao.init(n);

		for (int i = 0; i < n; i++) {

			for (int j = i + 1; j < n; j++) {

				if (c[i].r + c[j].r - eps < dis(c[i], c[j])) continue;

				double tmp = acos((c[i].x * c[j].x + c[i].y * c[j].y) / dis(c[i], cc) / dis(c[j], cc));

				bool flag = (c[i].x * c[j].y - c[i].y * c[j].x) >= 0;

				gao.add_Edge(i, j, flag ? tmp : -tmp);

				gao.add_Edge(j, i, flag ? -tmp : tmp);

			}

		}

		printf("%s\n", !gao.negativeCycle() ? "YES" : "NO");

	}

	return 0;

}

G:

#include <cstdio>

#include <cstring>

#include <vector>

#include <algorithm>

using namespace std;

const int N = 100005;

int n;

struct Man {

	int a, b, id;

} man[N];

bool cmp(Man a, Man b) {

	if (a.a == b.a) return a.b > b.b;

	return a.a < b.a;

}

int dp[N], save[N], sn;

bool judge(Man a, Man b) {

	if (a.a <= b.a && a.b >= b.b) return false;

	if (a.a >= b.a && a.b <= b.b) return false;

	return true;

}

int main() {

	while (~scanf("%d", &n)) {

		for (int i = 1; i <= n; i++) {

			scanf("%d%d", &man[i].a, &man[i].b);

			man[i].id = i;

		}

		sort(man + 1, man + n + 1, cmp);

		memset(dp, 0, sizeof(dp));

		sn = 0;

		save[sn++] = 0;

		for (int i = 1; i <= n; i++) {

			int v = lower_bound(save, save + sn, man[i].b) - save;

			save[v] = man[i].b;

			if (v == sn) sn++;

			dp[i] = v;

		}

		int sum = sn - 1;

		printf("%d\n", sum);

		int bo = 0;

		for (int i = n; i >= 1; i--) {

			if (dp[i] == sum) {

				if (bo) printf(" ");

				else bo = 1;

				printf("%d", man[i].id);

				sum--;

			}

		}

		printf("\n");

	}

	return 0;

}

H:

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

typedef long long ll;

const int MAXN = 2005;

struct bign {

	int len;

	ll num[MAXN];

	bign () {

		len = 0;

		memset(num, 0, sizeof(num));

	}

	bign (ll number) {*this = number;}

	bign (const char* number) {*this = number;}

	void DelZero ();

	void Put ();

	void operator = (ll number);

	void operator = (char* number);

	bool operator <  (const bign& b) const;

	bool operator >  (const bign& b) const { return b < *this; }

	bool operator <= (const bign& b) const { return !(b < *this); }

	bool operator >= (const bign& b) const { return !(*this < b); }

	bool operator != (const bign& b) const { return b < *this || *this < b;}

	bool operator == (const bign& b) const { return !(b != *this); }

	void operator ++ ();

	void operator -- ();

	bign operator + (const int& b);

	bign operator + (const bign& b);

	bign operator - (const int& b);

	bign operator - (const bign& b);

	bign operator * (const ll& b);

	bign operator * (const bign& b);

	bign operator / (const ll& b);

	//bign operator / (const bign& b);

	int operator % (const int& b);

};

/*Code*/

int prime[10005], pn = 0, vis[10005];

void getprime() {

	for (int i = 2; i < 10000; i++) {

		if (vis[i]) continue;

		prime[pn++] = i;

		for (int j = i * i; j < 10000; j += i)

			vis[j] = 1;

	}

}

const int N = 105;

int m, n;

int A[N][N];

int gauss() {

	int i = 0, j = 0, k, r, u;

	while (i < m && j < n) {

		r = i;

		for (k = i; k < m; k++)

			if (A[k][j]) {r = k; break;}

		if (A[r][j]) {

			if (r != i) for (int k = 0; k <= n; k++) swap(A[r][k], A[i][k]);

			for (u = i + 1; u < m; u++) if (A[u][j])

				for (k = i; k <= n; k++) A[u][k] ^= A[i][k];

			i++;

		}

		j++;

	}

	return i;

}

int main() {

	getprime();

	while (~scanf("%d%d", &m, &n)) {

		memset(A, 0, sizeof(A));

		int num;

		for (int k = 0; k < n; k++) {

			scanf("%d", &num);

			for (int i = 0; i < m; i++) {

				if (num % prime[i] == 0) {

					int cnt = 0;

					while (num % prime[i] == 0) {

						num /= prime[i];

						cnt++;

					}

					if (cnt % 2) A[i][k] = 1;

				}

			}

		}

		int sb = gauss();

		bign ans = 1;

		for (int i = 0; i < n - sb; i++) {

			ans = ans + ans;

		}

		ans = ans - 1;

		ans.Put();

		printf("\n");

	}

	return 0;

}

/*********************************************/

void bign::DelZero () {

	while (len && num[len-1] == 0)

		len--;

	if (len == 0) {

		num[len++] = 0;

	}

}

void bign::Put () {

	for (int i = len-1; i >= 0; i--)

		printf("%lld", num[i]);

}

void bign::operator = (char* number) {

	len = strlen (number);

	for (int i = 0; i < len; i++)

		num[i] = number[len-i-1] - '0';

	DelZero ();

}

void bign::operator = (ll number) {

	len = 0;

	while (number) {

		num[len++] = number%10;

		number /= 10;

	}

	DelZero ();

}

bool bign::operator < (const bign& b) const {

	if (len != b.len)

		return len < b.len;

	for (int i = len-1; i >= 0; i--)

		if (num[i] != b.num[i])

			return num[i] < b.num[i];

	return false;

}

void bign::operator ++ () {

	int s = 1;

	for (int i = 0; i < len; i++) {

		s = s + num[i];

		num[i] = s % 10;

		s /= 10;

		if (!s) break;

	}

	while (s) {

		num[len++] = s%10;

		s /= 10;

	}

}

void bign::operator -- () {

	if (num[0] == 0 && len == 1) return;

	int s = -1;

	for (int i = 0; i < len; i++) {

		s = s + num[i];

		num[i] = (s + 10) % 10;

		if (s >= 0) break;

	}

	DelZero ();

}

bign bign::operator + (const int& b) {

	bign a = b;

	return *this + a;

}

bign bign::operator + (const bign& b) {

	int bignSum = 0;

	bign ans;

	for (int i = 0; i < len || i < b.len; i++) {

		if (i < len) bignSum += num[i];

		if (i < b.len) bignSum += b.num[i];

		ans.num[ans.len++] = bignSum % 10;

		bignSum /= 10;

	}

	while (bignSum) {

		ans.num[ans.len++] = bignSum % 10;

		bignSum /= 10;

	}

	return ans;

}

bign bign::operator - (const int& b) {

	bign a = b;

	return *this - a;

}

bign bign::operator - (const bign& b) {

	ll bignSub = 0;

	bign ans;

	for (int i = 0; i < len || i < b.len; i++) {

		bignSub += num[i];

		if (i < b.len)

			bignSub -= b.num[i];

		ans.num[ans.len++] = (bignSub + 10) % 10;

		if (bignSub < 0) bignSub = -1;

		else bignSub = 0;

	}

	ans.DelZero();

	return ans;

}

bign bign::operator * (const ll& b) {

	ll bignSum = 0;

	bign ans;

	ans.len = len;

	for (int i = 0; i < len; i++) {

		bignSum += num[i] * b;

		ans.num[i] = bignSum % 10;

		bignSum /= 10;

	}

	while (bignSum) {

		ans.num[ans.len++] = bignSum % 10;

		bignSum /= 10;

	}

	return ans;

}

bign bign::operator * (const bign& b) {

	bign ans;

	ans.len = 0;

	for (int i = 0; i < len; i++){

		int bignSum = 0;

		for (int j = 0; j < b.len; j++){

			bignSum += num[i] * b.num[j] + ans.num[i+j];

			ans.num[i+j] = bignSum % 10;

			bignSum /= 10;

		}

		ans.len = i + b.len;

		while (bignSum){

			ans.num[ans.len++] = bignSum % 10;

			bignSum /= 10;

		}

	}

	return ans;

}

bign bign::operator / (const ll& b) {

	bign ans;

	ll s = 0;

	for (int i = len-1; i >= 0; i--) {

		s = s * 10 + num[i];

		ans.num[i] = s/b;

		s %= b;

	}

	ans.len = len;

	ans.DelZero();

	return ans;

}

int bign::operator % (const int& b) {

	bign ans;

	int s = 0;

	for (int i = len-1; i >= 0; i--) {

		s = s * 10 + num[i];

		ans.num[i] = s/b;

		s %= b;

	}

	return s;

}