## 【Codeforces 800C】Vulnerable Kerbals

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 5000000;
const int M = 10000;

int n,m,tot,ans,vis[N],id[N],in[M],num[M];
vector<int> que[M],vout;

inline int read() {
char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

int gcd(int a, int b) {
return b? gcd(b, a%b): a;
}

inline void AddEdge(int u, int v) {
static int E = 1; in[u]++;
to[++E] = u; nxt[E] = head[v]; head[v] = E;
}

void solve(int w) {
f[w] = que[w].size() + (itr[w]?f[itr[w]]:0);
ans = max(ans, f[w]);
for (int i=head[w];i;i=nxt[i]) {
if (f[w] > f[itr[to[i]]]) itr[to[i]] = w;
if (--in[to[i]] == 0) solve(to[i]);
}
}

void exgcd(int a, int b, LL &x, LL &y) {
if (b) {exgcd(b, a%b, y, x); y -= a / b * x;}
else {x = 1; y = 0;}
}

inline int REV(int a, int z) {
int tmp = gcd(a, m), b; LL x, y;
a /= tmp; z /= tmp; b = m / tmp;
exgcd(a, b, x, y);
return x * z % m;
}

void print(int w, int v) {
for (int i=0;i<=que[w].size()-1;i++) {
int nv = que[w][i], rev = REV(v, nv);
vout.push_back((rev+m)%m); v = nv;
}
if (itr[w]) print(itr[w], v);
}

int main() {
for (int i=1;i<=n;i++) vis[read()] = 1;
for (int i=1;i<m;i++) if (!vis[i]) {
int tmp = gcd(m, i);
if (!id[tmp]) id[tmp] = ++tot, num[tot] = tmp;
que[id[tmp]].push_back(i);
}
for (int i=1;i<=tot;i++) {
for (int j=1;j<=tot;j++) {
if (num[j] > num[i] && num[j] % num[i] == 0) {
}
}
}
for (int i=1;i<=tot;i++) if (!in[i]) solve(i);
for (int i=1;i<=tot;i++) if (f[i] == ans) {print(i, 1); break;}
if (!vis[0]) vout.push_back(0); cout<<vout.size()<<endl;
for (int i=0;i<=vout.size()-1;i++) printf("%d ",vout[i]);
return 0;
}


## 【Codeforces 715C】Digit Tree

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 200000 + 9;

int n,MOD; LL vout;

inline int read() {
char c=getchar(); int f=1,ret=0;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret * f;
}

inline void Add_Edge(int u, int v, int w) {
static int T = 0;
to[++T] = v; nxt[T] = head[u]; head[u] = T; cost[T] = w;
to[++T] = u; nxt[T] = head[v]; head[v] = T; cost[T] = w;
}

void gcd(int a, LL &x, int b, LL &y) {
if (!b) {x = 1, y = 0;}
else {gcd(b,y,a%b,x);y-=a/b*x;}
}

inline int gcd(int a, int b) {
static LL x,y;
gcd(a,x,b,y);
return (x % MOD + MOD) % MOD;
}

namespace Node_Decomposition{
#define ND Node_Decomposition
const int INF = 1e9;
int tot,node_sz,root,cur;
int sum[N],dep[N],vis[N];
map<int,int> cnt;

void Get_Root(int w, int f) {
sum[w] = 1; int mx = 0;
for (int i=head[w];i;i=nxt[i]) {
if (to[i] != f && !vis[to[i]]) {
Get_Root(to[i], w);
sum[w] += sum[to[i]];
mx = max(mx, sum[to[i]]);
}
}
mx = max(mx, node_sz - sum[w]);
if (mx < cur) cur = mx, root = w;
}

void DFS(int w, int f, int delta, LL p, int val) {
cnt[val] += delta;
for (int i=head[w];i;i=nxt[i]) {
if (!vis[to[i]] && to[i] != f) {
DFS(to[i], w, delta, p * 10 % MOD, (val + cost[i] * p) % MOD);
}
}
}

void cal(int w, int f, int t, LL val) {
vout += cnt[(-val*REV[t]%MOD+MOD)%MOD];
for (int i=head[w];i;i=nxt[i]) {
if (!vis[to[i]] && to[i] != f) {
cal(to[i], w, t+1, (val * 10 + cost[i]) % MOD);
}
}
}

void solve(int w, int sz) {
vis[w] = 1; cnt.clear();
for (int i=head[w];i;i=nxt[i]) {
if (!vis[to[i]]) {
DFS(to[i], w, 1, 10 % MOD, cost[i] % MOD);
}
}
vout += cnt[0]; cnt[0]++;
for (int i=head[w];i;i=nxt[i]) {
if (!vis[to[i]]) {
DFS(to[i], w, -1, 10 % MOD, cost[i] % MOD);
cal(to[i], w, 1, cost[i] % MOD);
DFS(to[i], w, 1, 10 % MOD, cost[i] % MOD);
}
}
for (int i=head[w];i;i=nxt[i]) {
if (!vis[to[i]]) {
node_sz = sum[to[i]] > sum[w] ? sz - sum[w] : sum[to[i]];
cur = INF; Get_Root(to[i], w);
solve(root, node_sz);
}
}
}

inline void solve() {
cur = INF; node_sz = n;
Get_Root(1,1);
solve(root,n);
}
};

int main() {
for (int i=1,u,v,w;i<n;i++) {
Add_Edge(u + 1, v + 1, w);
}
REV[0] = 1; REV[1] = gcd(10, MOD);
for (int i=2;i<=n;i++)
REV[i] = (LL)REV[i-1] * REV[1] % MOD;
ND::solve();
printf("%lld\n",vout);
return 0;
}


## 【BZOJ 4522】[Cqoi2016] 密钥破解

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

LL e,N,c,r,d,n;

void EX_GCD(LL &x, LL a, LL &y, LL b) {
if (!b) {x = 1; y = 0;}
else {EX_GCD(y,b,x,a%b); y -= a/b*x;}
}

inline LL EX_GCD(LL a, LL b) {
LL t1, t2;
EX_GCD(t1,a,t2,b);
return (t1%r + r) % r;
}

inline LL Mul(LL a, LL b) {
LL ret = 0;
while (b) {
if (b&1) ret  = (ret + a) % N;
a = a*2 % N; b >>= 1;
}
return ret;
}

inline LL pow(LL w, LL t) {
LL ret = 1;
while (t) {
if (t & 1) ret = Mul(ret, w);
w = Mul(w, w); t >>= 1;
}
return ret;
}

inline LL GCD(LL a, LL b){
while (b) a = a % b, swap(a, b);
return a;
}

inline void Decompose(){
for (int seed=(rand()&32767)%(N-1)+1;!r;seed=(rand()&32767)%(N-1)+1) {
LL w = rand() % (N-1) + 1, seg=2, tmp = -1, cnt = 0, gcd;
while (w != tmp && !r) {
gcd = GCD(abs(w-tmp), N);
if (1 < gcd && gcd < N) r = Mul(N/gcd-1,gcd-1);
if (++cnt == seg) seg <<= 1, tmp = w;
w = (Mul(w,w) + seed) % (N-1) + 1;
}
}
}

int main(){
srand(999971);
cin>>e>>N>>c; Decompose();
d = EX_GCD(e,r); n = pow(c,d);
cout<<d<<' '<<n;
return 0;
}


## 【BZOJ 2242】[SDOI2011] 计算器

MD，老子好想杀人！ (╯‵□′)╯︵┻━┻

#include<cstdio>
#include<iostream>
#include<cmath>
#include<cstring>
#define LL long long
using namespace std;

const int MAXN = 100000;
const double EPS = 1e-5;

namespace Hash{
const int MOD = 99971;

inline void init(){
T = 0;
}

inline void insert(int w, int d){
val[T] = w; data[T] = d;
}

inline int find(int w){
if (val[i] == w) return data[i];
return -1;
}
};

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0'){ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

inline int quick_pow(int a,int b,int c){
int ret = 1; while (b) {
if (b & 1) ret = ((LL)ret * a) % c;
a = (LL)a*a%c; b >>= 1;
} return ret;
}

int GCD(int a, int b){return b?GCD(b,a%b):a;}

void EX_GCD(int a, int b, int &x, int &y){
if (!b) x=1, y=0;
else EX_GCD(b,a%b,y,x), y-=a/b*x;
}

inline int EX_GCD(int a, int b, int c) {
int ret,tmp,gcd=GCD(a,b);
if (c%gcd) return -1;
else {
EX_GCD(a/gcd,b/gcd,ret,tmp);
ret = (((LL)c/gcd*ret) % b + b) % b;
return ret;
}
}

inline void solve(int a, int b, int c) {
int ret = EX_GCD(a,c,b);
if (~ret) printf("%d\n",ret);
else printf("Orz, I cannot find x!\n");
}

inline void BSGS(int a, int b, int c) {
Hash::init(); a %= c; b %= c;
if (!a && b > 1) {printf("Orz, I cannot find x!\n"); return;}

int lim = int(ceil(sqrt(c))+EPS);
for (int i=0,w=1;i<=lim;i++) {
if (w == b) {printf("%d\n",i); return;}
Hash::insert(w,i);
w = ((LL)w*a) % c;
}

int w_ori = quick_pow(a,lim,c), rev_ori = quick_pow(w_ori,c-2,c);
for (int i=1,w=w_ori,rev=rev_ori;i<=lim;i++) {
int tmp = Hash::find(((LL)rev*b) % c);
if (tmp > -1) {printf("%d\n",i*lim+tmp); return;}
w = ((LL)w*w_ori) % c;
rev = ((LL)rev*rev_ori) % c;
}
printf("Orz, I cannot find x!\n");
}

int main(){