【Codeforces 800C】Vulnerable Kerbals

相关链接

题目传送门:http://codeforces.com/contest/800/problem/C

解题报告

写一写发现前缀积与$m$的$\gcd$是一个递增的关系,依次为倍数
于是我们将$0 \sim m-1$按照与$m$的$\gcd$分类
然后就是在拓扑图上搞一搞$DP$,输出的时候用拓展欧几里得求一发逆元
总的时间复杂度:$O(n \log n)$

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];
int head[M],nxt[N],to[N],f[M],itr[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() {
	n = read(); m = read();
	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) {
				AddEdge(i, j); 
			}
		}
	}
	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】算术天才⑨与等差数列

相关链接

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4373
神犇题解:http://blog.csdn.net/TA201314/article/details/51177011

解题报告

首先,假如一个区间满足以下三个条件那么该区间一定合法:

$\%k$后相等
每一个数互不相同
区间和等于某一特定值

后两个条件都可以用线段树维护
问题就是第一个条件非常麻烦

先来考虑一种简单的Hash方式:记录区间的平方和
这样的话,我们可以$O(1)$计算基准值,$O(\log n)$判断是否等于基准值

但众所周知,Hash是不优雅的
于是我们可以先做一个差分序列,然后维护差分序列相邻两项的$\gcd$
考虑如果所有数的差都是$k$的整数倍,那么这些数$ \bmod \ k$之后肯定就相等啦!

另外的话,区间GCD配合差分的题,也不是第一次见了
之前NOI还考过一道:魔幻棋盘
以后和GCD相关的题目要想一想差分行不行啊!

【BZOJ 4522】[Cqoi2016] 密钥破解

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4522
数据生成器:http://paste.ubuntu.com/23140343/

这题,我觉得唯一的难点在分解因数
因为忘了棒棒糖怎么写,于是考试的时候只能写了50分的暴力
话说CQOI怎么能考模板呢?YLUL)A7V{OMTL8]~RL2VL$8

#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] 同余方程

题目传送门:http://oi.cdshishi.net:8080/Problem/256
离线版题目:http://paste.ubuntu.com/17895904/

求逆元的板题,顺便补了exGCD,么么哒!

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