Category: 欧几里得算法

相关链接

题目传送门：http://agc015.contest.atcoder.jp/tasks/agc015_f

解题报告

我们写出使答案最大且值最小的序列，不难发现这是一个斐波那契数列
进一步发现，这条主链的每一个点只会引申出一条支链，且支链不会再分
所以我们可以暴力算出了$\log n$条链，共$\log ^ 2 n$对数，然后暴力算贡献

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];
 
inline LL read() {
	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--) {
		LL A = read(), B = read();
		solve(min(A, B), max(A, B));
	}
	return 0;
}

相关链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2852
神犇题解：http://blog.csdn.net/rzo_kqp_orz/article/details/52497951

解题报告

设最终区间包含的数为$t$
那么我们就是要求解这个不等式：$ka \le t \le kb$
我们分两种情况讨论：

1. $\lfloor a \rfloor \ne \lfloor b \rfloor$

这样的话，显然答案为$k = 1$

2. $\lfloor a \rfloor = \lfloor b \rfloor$

这样的话，我们先可以刨开$a,b$的整数部分
于是答案变为这个不等式的解：$s \cdot \frac{1}{b – \lfloor a \rfloor} \le k \le s \cdot \frac{1}{a – \lfloor a \rfloor}$

我们发现最后的式子与原问题形式相同，于是可以递归求解
更进一步，我们每次将较大的数减去较小的数，然后交换位置，这是典型的类欧几里得算法
于是我们就可以在：$O(\log n)$的时间复杂度内递归求解原问题了

至于代码，显然需要用高精度
但我不会py QwQ

题目大意

求$(b)\oplus(b+a)\oplus(b+2a)\oplus\cdots\oplus(b+(n-1)a)$
其中$n,a,b\le10^9$

解题报告

因为是二进制，所以我们每一位分开考虑
又因为数$a$二进制下第$k$位的奇偶性与$a>>(k-1)$的奇偶性相同
所以对于第$k$位，我们实际是要求$\sum\limits_{x=0}^{n-1}{\left\lfloor {\frac{{ax + b}}{{{2^k}}}} \right\rfloor}$，我们将其一般化：求解$f(a,b,c,n)=\sum\limits_{x=0}^{n}{\left\lfloor {\frac{{ax + b}}{{{c}}}} \right\rfloor}$

设$s(x)=\sum\limits_{i=1}^{x}{i}$。为了只讨论$a,b<c$的情况，我们先来预处理一下：

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$

之后我们就可以施展膜法了：
设$m=\lfloor\frac{an+b}{c}\rfloor$
那么原式$=\sum\limits_{x=0}^{n}{\sum\limits_{y=0}^{m}{[y<\lfloor\frac{ax+b}{c}\rfloor]}}$
把$y<\lfloor\frac{ax+b}{c}\rfloor$提出来，可以化简：
$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$
那么原式$=\sum\limits_{y=0}^{m}{\sum\limits_{x=0}^{n}{[x>\lfloor\frac{cy+c-b-1}{a}\rfloor]}}=n(m+1)-\sum\limits_{y=0}^m{\lfloor\frac{cy+c-b-1}{a}\rfloor}$
相当于$f(a,b,c,n)=n(m+1)-f(c,c-b\%c-1,a\%c,m)$
窝萌发现，这货的形式简直和辗转相处搞$gcd$一模一样
于是这货的复杂度也是$O(\log n)$的

当然这题还有一种数形结合的推法
推出来式子略有不同，不过时间复杂度仍然为$O(\log n)$
不过本文这种推法似乎更优？据敦敦敦讲，这货可以推广到高维
但我不会 QwQ

Code

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

inline int read() {
	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() {
	for (int T=read(),a,b,n;T;T--) {
		n = read(); b = read(); 
		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;
}

题目传送门：http://codeforces.com/problemset/problem/711/E
官方题解：http://codeforces.com/blog/entry/46830
中文题面及题解：https://blog.sengxian.com/solutions/cf-711e

这个题重点不在推概率，而在Legendre’s formula
其实难点就是要求在取MOD之前就约分，这个就很麻烦了，只有用上面那个定理

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

inline LL read(){
	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(){
	LL n = read(), k = read(), tn = pow(2,n);
	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:如果不知道上面的那个定理，貌似自己推也是可以推出来的？