## 【AtCoder】[Grand Contest 015 F] Kenus the Ancient Greek

### Code

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

const int MOD = 1000000007;
const int LOG = 100;

vector<pair<LL, LL> > num[LOG];

char c = getchar(); LL ret = 0, f = 1;
for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
return ret * f;
}

inline void solve(LL A, LL B) {
if (A < num[2][0].first || B < num[2][0].second) {
printf("1 %d\n", A * B % MOD);
return;
}
for (int i = 2; i < LOG; i++) {
if (A < num[i + 1][0].first || B < num[i + 1][0].second) {
int cnt = 0;
for (int j = 0; j < (int)num[i].size(); j++) {
LL a = num[i][j].first, b = num[i][j].second;
cnt = (cnt + (a <= A && b <= B? (B - b) / a + 1: 0)) % MOD;
cnt = (cnt + (b <= A && a <= B? (A - b) / a + 1: 0)) % MOD;
}
printf("%d %d\n", i, cnt);
return;
}
}
}

inline void prework() {
num[0] = vector<pair<LL,LL> >{make_pair(1, 1)};
for (int i = 1; i < LOG; i++) {
for (int j = 0; j < (int)num[i - 1].size(); ++j) {
LL a = num[i - 1][j].first, b = num[i - 1][j].second;
num[i].push_back(make_pair(b, a + b));
}
LL a = num[i - 1][0].first, b = num[i - 1][0].second;
num[i].push_back(make_pair(a + b, 2 * a + b));
}
}

int main() {
prework();
for (int T = read(); T; T--) {
solve(min(A, B), max(A, B));
}
return 0;
}


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


## 【日常小测】超级绵羊异或

### 解题报告

1. 若$a \ge c$那么显然$f(a,b,c,n) = f(a \% c,b,c,n) + \lfloor\frac{a}{c}\rfloor \cdot s(n)$
2. 若$b \ge c$那么显然$f(a,b,c,n) = f(a,b\%c,c,n) + \lfloor\frac{b}{c}\rfloor \cdot n$

$y<\lfloor\frac{ax+b}{c}\rfloor = c(y+1) \le ax+b = cy+c-b-1<ax=x>\lfloor\frac{cy+c-b-1}{a}\rfloor$

### Code

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

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

LL cal(LL a, LL b, LL c, LL n) {
if (a >= c) return (((n-1)*n/2)*(a/c)&1) ^ cal(a%c, b, c, n);
if (b >= c) return (n * (b/c) & 1) ^ cal(a, b%c, c, n);
if (!a) return (b/c) * n & 1;
LL nw = (a * (n - 1) + b) / c;
return ((n-1) * nw & 1) ^ cal(c, c - b - 1, a, nw);
}

int main() {
a = read(); LL c = 1, ans = 0;
if (!b) {printf("%d\n",(n&1)?a:0); continue;}
for (int i=0;i<=60;i++,c<<=1)
ans += cal(a, b, c, n) * c;
printf("%lld\n",ans);
}
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;
}


## 【Codeforces 711E】ZS and The Birthday Paradox

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

const LL MOD = 1000003;

char c=getchar(); LL 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 LL pow(LL w, LL t) {
LL ret = 1;
while (t) {
if (t & 1) ret = ret*w % MOD;
w = w*w % MOD; t >>= 1;
}
return ret;
}

inline bool judge(LL n, LL k) {
LL w = 1;
for (int i=1;i<=n;i++) {
w *= 2;
if (w >= k) return false;
} return true;
}

int main(){
if (judge(n,k)) cout<<1<<' '<<1;
else {
LL t1, t2, cnt = (k-1) - __builtin_popcountll(k-1), gcd = pow(pow(2,cnt),MOD-2);
if (k >= MOD) t1 = 0; else {t1 = 1; for (int i=1;i<k;i++) t1 = t1 * (tn - i) % MOD;}
t2 = pow(pow(2,n),k-1); t2 = t2 * gcd % MOD; t1 = t1 * gcd % MOD; t1 = ((t2 - t1)% MOD + MOD) % MOD;
cout<<t1<<' '<<t2;
}
return 0;
}


ps:如果不知道上面的那个定理，貌似自己推也是可以推出来的？

## 【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(){
if (ty == 1) printf("%d\n",quick_pow(a,b,c));
else if (ty == 2) solve(a,b,c);
else BSGS(a,b,c);
}
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;
}