Andrew Stnkevich's Conttest(1)
22425 ワード
Andrew Stnkevich's Conttest(1)
半分打って家を出て、帰って来てやっと補完しました。各種の大きな数はまたjavaに行くことができません。卵が痛くてたまらないです
A:置換循環節によって、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:行列は素早くべき乗し、両関係を確立したら、行列を作って素早くべき乗すればいいです。
幾何学的な問題で、限られた視角と形成されるかどうかを判断します。spfaを利用して負のリングを判定すればいいです。
G:LIS、まずxを押して小さい時から大きい時まで、yを押して大きい時から小さい順に並べて、このようにyに対してlisをするのは解答で、出力のパスのため、dp配列を開けて各位置の解答を記録して、それから一回を掃除して任意の出力の方案をすればいいです。
H:ガウスの消元、大きい白書の上で例題とほぼ同じで、完全な平方の数のすべての因子は必然的に偶数で、このように異種あるいは方程式を創立することができて、それから計算して便元の個数xから来て、解答は2^x-1です。
コード:
A:
半分打って家を出て、帰って来てやっと補完しました。各種の大きな数はまたjavaに行くことができません。卵が痛くてたまらないです
A:置換循環節によって、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:行列は素早くべき乗し、両関係を確立したら、行列を作って素早くべき乗すればいいです。
幾何学的な問題で、限られた視角と形成されるかどうかを判断します。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("
");
}
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
");
for (int i = 0; i < 2 * tot; i += 2)
printf("%d
", 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
");
}
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
", ans);
for (int i = 0; i < on; i++)
printf("%d%c", out[i], i == on - 1 ? '
' : ' ');
}
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
", 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
", 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
", !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
", 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("
");
}
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("
");
}
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;
}