## 【BZOJ 3025】[Balkan2003] Farey数列

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

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

### 相关拓展

$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];

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


## 【算法笔记】线性筛 与 线性递推

get_phi_prime_mu_in_linear_time

ps:之前好像说必须先O(n)筛出素数？现在发现好像不需要QAQ（模板参考BZOJ_2705）

## 【POJ 1284】Primitive Roots

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