【BZOJ 3025】[Balkan2003] Farey数列

题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3025
数据加强版:http://oi.cdshishi.net/contestoi/problem_show.php?pid=1063
数据生成器(要求支持假分数):http://paste.ubuntu.com/23391949/

好久没有做推式子的题目啦!
首先这题可以用Farey sequence直接做:https://en.wikipedia.org/wiki/Farey_sequence
具体实现上可能需要用Stern–Brocot tree:https://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree
上述做法把此题变成裸题,然而不知道上面的东西怎么办?
下面说一说使用莫比乌斯函数的O(nlog(n^2))的做法
注:以下讨论均针对于数据加强版,BZOJ上的原题可能不需要这么复杂

最外层先搞一个二分,假设二分到某一个值使得小于等于他的分数刚好有k个
那么我们只需要枚举分母,找到其中最大的一个输出即可
另外,这里的二分只能定分母、二分分子。不能够直接二分小数,原因待会儿说。
考虑到精度问题,我们定分母EPS=1e10(实际上也只能定为1e10,因为小了精度不够,大了要炸long long)

假设二分的分子为k,则现在我们需要求解的便是:\(\sum\limits_{y = 1}^n {\sum\limits_{x = 1}^{\left\lfloor {\frac{{yk}}{{EPS}}} \right\rfloor } {\sum\limits_{d|x,y} {\mu (d)} } } \)
稍微变形一下可以得到:\(\sum\limits_{d = 1}^n {\mu (d)\sum\limits_{y = 1}^{\left\lfloor {\frac{n}{d}} \right\rfloor } {\sum\limits_{x = 1}^{\left\lfloor {\frac{{\left\lfloor {\frac{{y \cdot d \cdot k}}{{EPS}}} \right\rfloor }}{d}} \right\rfloor } 1 } } \)
注意到x的上限有两个取整函数,因为取整函数有这个性质:\(\left\lfloor {\frac{{\left\lfloor {\frac{{\rm{y}}}{a}} \right\rfloor }}{b}} \right\rfloor = \left\lfloor {\frac{y}{{ab}}} \right\rfloor\)
所以才可以去掉上面的那个取整函数,这也是为什么不能直接二分实数,因为实数去不掉那个取整函数

我们继续推导,再次化简以后可以得到:\(\sum\limits_{d = 1}^n {\mu (d)\sum\limits_{y = 1}^{\left\lfloor {\frac{n}{d}} \right\rfloor } {\sum\limits_{x = 1}^{\left\lfloor {\frac{{yk}}{{EPS}}} \right\rfloor } 1 } } \)
这样的话,就可以线性处理后两个Σ,然后O(n)枚举d来计算了
另外还有一个小细节:x不仅受到分数值的限制,还受到n的限制,所以那里还需要特判一下

这题还有一种类似的做法,但可避免炸long long的风险:
考虑仪仗队那个题,因为方队左右对称,于是总可以把问题划归到方阵的右下部分
然后二分右下部分的斜率(定分母为n,二分分子)
二分到分子差只有1的时候,就暴力取出那个区间的所有分数,排序输出

这题我写的代码是第一种方式的,精度巨坑,必须是1e10,且不能有任何实数运算

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

const int N = 100000+9;
const LL EPS = 1e10;

int pri[N],tot,n,cnt,mu[N];
LL f[N],K,vx,vy;
bool vis[N];

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

inline void Get_Mu() {
	mu[1] = 1;
	for (int i=2;i<=n;i++) {
		if (!vis[i]) pri[++tot] = i, mu[i] = -1; 
		for (int j=1;j<=tot&&i*pri[j]<=n;j++) {
			vis[i*pri[j]] = 1;
			if (i%pri[j]) mu[i*pri[j]] = -mu[i];
			else {mu[i*pri[j]] = 0; break;}
		}
	}
}

inline LL Get(LL w) {
	for (int i=1;i<=n;i++) f[i] = i * w / EPS;
	for (int i=2;i<=n;i++) f[i] += f[i-1];
	
	LL ret = 0, sta;
	for (int i=1;i<=n;i++) {
		sta = (LL)EPS * n / (w * i);
		ret += f[min(n/(LL)i, sta)] * mu[i];
		if (sta < n/i) ret += (n/i) * (n/i - sta) * mu[i];
	}
   	return ret;
}

inline void Get_Ans(LL w) {
	for (int y=1,x;y<=n;y++) {
		x = min((LL)n, w * y / EPS);
		if (x && (vx * y < vy * x || !vx)) 
			vx = x, vy = y;
	}
	printf("%lld %lld\n", vx, vy);
}

int main(){
	cin>>n>>K;
	Get_Mu();
	
	LL l=1, r=(LL)n*EPS, mid, ret;
	while (l <= r) {
		mid = l + r >> 1;
		if (Get(mid) <= K) ret = mid, l = mid + 1;
		else  r = mid - 1;
	}	
	Get_Ans(ret);
	return 0;
}

【日常小测】Fibonacci

相关连接

题目传送门:https://oi.qizy.tech/wp-content/uploads/2016/10/2016.10.19.pdf
官方题解:https://oi.qizy.tech/wp-content/uploads/2016/10/Fibonacci.pdf

解题报告

这个题目啊!有一个神奇的结论:\({F_i}|{F_j} \Rightarrow i|j\)
现在让我们来证明这个结论:

不难发现我们只需要证明:\({F_i}|{F_{i \cdot k}}\)
然后有一个明显的结论:fibonacci的通项公式在模意义下仍然适用
于是我们可以将整个数列%上\(F_i\)就可以证明啦!

当然还有一个奇怪的结论:\(\gcd ({f_i},{f_j}) = {f_{\gcd (i,j)}}\)
据说这货证明和上面的类似?

所以说这个题目线筛一下约数个数和约数的平方和就好辣!
另外,我的线筛姿势比较奇怪,不要学我啊!

相关拓展

$Fibonacci$数列还有很多妙妙的性质,以下列举一点:

  1. $gcd(f_n,f_m)=f_{gcd(n,m)}$
  2. ${f_n}^2+{f_{n-1}}^2 = f{2n+2}$
  3. $f_n \cdot (f_{n-1}+f_{n+1}) = f{2n+1}$
  4. 如果$f_k$能被$x$整除,则$f_{ki}$都可以被$x$整除

Code

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

const int N = 10000000+9;
const int MX = 10000000;
const int MOD = 1000000007;

int f1[N],f2[N],n,A,B,C,W,vout1,vout2;
int tot,pri[N],top[N],REV[50];
short vis[N],MN[N];

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

inline int pow(int w, int t) {
	int ret = 1;
	while (t) {
		if (t & 1) ret = (LL)ret * w % MOD;
		w = (LL)w * w % MOD; t>>= 1;
	}
	return ret;
}


inline void prework(){
	REV[0] = 1;
	for (int i=1;i<=30;i++) {
		REV[i] = pow(i,MOD-2);
	}
	
	f1[1] = 1; f2[1] = 1;
	for (int i=2;i<=MX;i++) {
		if (!vis[i]) {
			pri[++tot] = i;
			f1[i] = 2; 
			f2[i] = (1 + (LL)i * i) % MOD;
			MN[i] = 1; top[i] = (LL)i * i % MOD;
		}
		for (int j=1,to,sqr;j<=tot&&i*pri[j]<=MX;j++) {
			vis[to = i*pri[j]] = 1;
			sqr = (LL)pri[j] * pri[j] % MOD;
			if (i % pri[j]) {
				f1[to] = f1[i] * 2 % MOD;
				f2[to] = f2[i] * (1LL + sqr) % MOD;
				MN[to] = 1; 
				top[to] = (LL)f2[i] * sqr % MOD;
			} else {
				MN[to] = MN[i] + 1; 
				top[to] = (LL)top[i] * sqr % MOD;
				f1[to] = (f1[i] + (LL)f1[i]*REV[MN[i]+1]) % MOD;
				f2[to] = (f2[i] + top[to]) % MOD;
				break;
			}	
		}
	}
	for (int i=3;i<=MX;i++) {
		if (i % 2) {
			f1[i] += 1;
			f2[i] += 4;
		}
	}
}

int main(){
	freopen("fibonacci.in","r",stdin);
	freopen("fibonacci.out","w",stdout);
	n = read(); W = read(); 
	A = read(); B = read(); C = read();
	prework();
	
	for (int i=1;i<=n;i++,W=((LL)W*A+B)%C+1) {
		vout1 += f1[W]; vout2 += f2[W];
		vout1 %= MOD; vout2 %= MOD;
	}
	printf("%d %d\n",vout1,vout2);
	return 0;
}

【POJ 1284】Primitive Roots

题目传送门:http://poj.org/problem?id=1284

题目大意:给一个素数(>3),求原根的个数。
相关定理:如果一个数a有原根,则个数为\(\varphi (\varphi (a))\\)
定理证明:我不会QAQ,可以参考:wiki中的性质一栏

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

const int MAXN = 100000+9;
const int MX = 70000;

int pri[MAXN],tot,phi[MAXN];
bool tag[MAXN];

inline void Get_Phi(){
	phi[1] = 1;
	for (int i=2;i<=MX;i++) {
		if (!tag[i]) pri[++tot] = i, phi[i] = i-1;
		for (int j=1;j<=tot && pri[j]*i <= MX;j++) {
			tag[pri[j]*i] = 1;
			if (i % pri[j]) phi[pri[j]*i] = phi[i]*(pri[j]-1);
			else {phi[pri[j]*i] = phi[i]*pri[j]; break;}
		}
	}
}

int main(){
	Get_Phi(); int a;
	while (~scanf("%d",&a))	printf("%d\n",phi[a-1]);	
	return 0;
} 

我一定不会告诉你:其实我只是来水线性递推欧拉函数的QAQ