## 【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;

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]++;
}

void solve(int w) {
f[w] = que[w].size() + (itr[w]?f[itr[w]]:0);
ans = max(ans, f[w]);
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;
}


## 【BZOJ 4373】算术天才⑨与等差数列

### 解题报告

$\%k$后相等

## 【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;
}


## 【SOJ 256】[NOIP2012] 同余方程

#include<iostream>
#include<cstdio>
using namespace std;

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

int main(){
int a,b,x,y;
scanf("%d%d",&a,&b);
exGCD(a,b,x,y);
printf("%d\n",((x%b)+b)%b);
return 0;
}