[一]----------------------------------------------------------数论杂记，变换入门
[二]----------------------------------------------------------数论分块入门题
[三]----------------------------------------------------------莫比乌斯杂记
[四]----------------------------------------------------------杜教筛入门
[五]----------------------------------------------------------$Guass$消元入门
[六]----------------------------------------------------------$M\ddot{o}bius$反演的证明
[七]----------------------------------------------------------$Lucas$定理的证明
[八]----------------------------------------------------------欧拉函数的常用变换(更新)
[九]----------------------------------------------------------数论杂记，善于从细节发起突破
[十]----------------------------------------------------------数论杂记，gcd与斐波那契的小结论证明
[十一]--------------------------------------------------------exCRT(扩展中国剩余定理)证明
[十二]--------------------------------------------------------新操作：原根与指标
开始我们的数论盛宴
引理1：$\sum\limits_{i|n}\varphi(i)=n$。
证明：
我们这个式子的意思是什么呢？看一下：如果我们枚举1到n，每一个数表示枚举最大公约数，那么，我们查询1到n中有多少数与n的最大公约数是 i 。若gcd( j , n ) = i ，那么
$gcd(\frac{j}{i},\frac{n}{i})=1$。所以，每一个数算了且仅被算了一次，证毕。
引理2：$\sum\limits_{i=1}^n\sum\limits_{j=1}^{\lfloor\frac n i\rfloor}\varphi(i)=\sum\limits_{i=1}^{n}\sum\limits_{j|i}\varphi(i)$ 。
证明：啊啊啊，坑了我很久了啊有木有！！
我们考虑前面的式子与后面的式子中的$\varphi(i)$的个数。考虑左式，每一个$\varphi(i)$都被算了$\lfloor\frac{n}{i}\rfloor$次，显然，这个式子表示n当中有多少个数是i的倍数，所以，每一个i都会且只会被它的倍数筛掉。也就是说它有多少个倍数就只会被筛多少次。那么，等价的，我们对于每一个数它的约数都会进行枚举，且枚举次数是一定相等的，证毕。
题目：在此，我们介绍Divisor counting中较文的做法(Divisor counting?猛戳)
想法：首先，不难想到$\sum\limits_{i=1}^nf(i)=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{i}[j|i]$其中，[j|i]表示j|i这个事件的正确性。紧接着，我们又想到一个数论中常用的变换——$\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{i}[j|i]=\sum\limits_{i=1}^{n}\sum\limits_{j=1}^{\lfloor\frac{n}{i}\rfloor}[1]$。为什么呢？从[一]中我们其实就可以看出，在外层枚举底数，考虑有多少是这个底数的倍数？所以，左式和右式是等价的。所以，我们就可以将原本的式子化为了一个我们处理过的式子。接下来就是分块处理，在此不再赘述。附上丑陋的代码......
#include <iostream>
#include <cstdio>
using namespace std;
int main()
{
int n;
scanf("%d",&n);
long long ans=0;
for(int last,i=1;i<=n;i=last+1)//分块处理。
{
last=n/(n/i);
ans+=(last-i+1)*(n/i);
}
printf("%lld",ans);
return 0;
}
小结：对于每道题来讲，我们其实可以用更简单但并不直接的算法，可以大大提高效率，注意重复思考的意识(在此，鸣谢Edward♂Frog)。
$M\ddot{o}bius$一血。
bzoj2045 求$\sum\limits_{i=1}^{a}\sum\limits_{j=1}^{b}[gcd(i,j)=k]$
咳咳，先介绍一下莫比乌斯反演
$F(n)=\sum\limits_{d|n}f(d)$
$\Leftrightarrow f(n)=\sum\limits_{d|n}\mu(d)F(\frac{n}{d})$
或者有
$F(n)=\sum\limits_{n|d}f(d)$
$\Leftrightarrow f(n)=\sum\limits_{n|d}\mu(\frac{d}{n})F(d)$
然后，对于这道题，我们有
$\sum\limits_{i=1}^a\sum\limits_{j=1}^b[gcd(i,j)==k]$
$\Leftrightarrow\sum\limits_{i=1}^{\lfloor\frac{a}{k}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{b}{k}\rfloor}[gcd(i,j)==1]$
$\Leftrightarrow\sum\limits_{i=1}^{\lfloor\frac{a}{k}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{b}{k}\rfloor}\sum\limits_{d|gcd(i,j)}\mu(d)$
然后和[一]类似的，对于每一个gcd(i,j)枚举它的约数，我们可以进而枚举它的倍数，但是我们想在此介绍莫比乌斯反演。
所以，我们设f(n)=满足最大公约数是n的数的对数
F(n)表示满足最大公约数是n的倍数的数的对数。
显然的，我们有$F(n)=\sum\limits_{n|d}f(n)$.
进而，我们裸的莫比乌斯反演
有$f(n)=\sum\limits_{n|d}\mu(\frac{d}{n})F(d)$。
然后，我们能发现，F(n)的值是O(1)的，就是$\lfloor\frac{a}{n}\rfloor\cdot\lfloor\frac{b}{n}\rfloor$其中，a=a/k，b=b/k。
d的范围显然是max(a,b)。$O(10^6)$筛出$\mu$，$O(\frac{max(a,b)}{n})$算出答案即可。我们显然只需要f(1)的值。
最后，附上丑陋的代码... ...
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define maxn 1000000
using namespace std;
typedef long long ll;
int miu[maxn+10];
int prime[maxn];
int cnt;
bool v[maxn+10];
ll a,b;
ll F(ll i)//算出F[i]
{
return (a/i)*(b/i);
}
void original()//线性筛出miu
{
miu[1]=1;
for(int i=2;i<=maxn;i++)
{
if(!v[i])
{
prime[++cnt]=i;
miu[i]=-1;
}
for(int j=1;j<=cnt&&i*prime[j]<=maxn;j++)
{
v[i*prime[j]]=true;
if(i%prime[j]==0)
{
miu[i*prime[j]]=0;
break;
}
miu[i*prime[j]]=-miu[i];
}
}
}
int main()
{
// int a,b,k;
int k;
original();
scanf("%lld%lld%d",&a,&b,&k);
if(!k)
{
printf("%d\n",0);
return 0;
}
a/=k,b/=k;//重要
if(a>b) swap(a,b);
ll ans=0;
for(ll i=1;i<=a;i++)
{
ans+=miu[i]*F(i);
}
printf("%lld\n",ans);
return 0;
}
好东西
2.另一种方法
bzoj 1101 Zap
几乎同样的题目，但是多组数据。莫比乌斯显然T，我们用分块。
$\sum\limits_{i=1}^a\sum\limits_{j=1}^b[gcd(i,j)==k]$
$\Rightarrow\sum\limits_{i=1}^{\lfloor\frac{a}{k}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{b}{k}\rfloor}[gcd(i,j)==1]$
$\Rightarrow\sum\limits_{i=1}^{\lfloor\frac{a}{k}\rfloor}\sum\limits_{j=1}^{\lfloor\frac{b}{k}\rfloor}\sum\limits_{d|gcd(i,j)}\mu(d)$
$\Rightarrow\sum\limits_{d=1}^{min(\lfloor\frac{a}{k}\rfloor,\lfloor\frac{b}{k}\rfloor)}\mu(d)\lfloor\frac{\lfloor\frac{a}{k}\rfloor}{k}\rfloor\lfloor\frac{\lfloor\frac{b}{k}\rfloor}{k}\rfloor$
最后，附上丑陋的代码... ...
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int tot;
int mu[50005],before[50005],pri[50005];
bool mark[50005];
void original()
{
mu[1]=1;
for(int i=2;i<=50000;i++)
{
if(!mark[i])pri[++tot]=i,mu[i]=-1;
for(int j=1;j<=tot&&i*pri[j]<=50000;j++)
{
mark[i*pri[j]]=1;
if(i%pri[j]==0){mu[i*pri[j]]=0;break;}
else mu[i*pri[j]]=-mu[i];
}
}
for(int i=1;i<=50000;i++)
before[i]=before[i-1]+mu[i];
}
int dispose(int n,int m)
{
if(n>m) swap(n,m);
int ans=0,pos;
for(int i=1;i<=n;i=pos+1)
{
pos=min(n/(n/i),m/(m/i));
ans+=(before[pos]-before[i-1])*(n/i)*(m/i);
}
return ans;
}
int main()
{
original();
int cases;
scanf("%d",&cases);
while(cases--)
{
int a,b,d;
scanf("%d%d%d",&a,&b,&d);
printf("%d\n",dispose(a/d,b/d));
}
return 0;
}
好东西++
杜教筛qwq
$\because\sum\limits_{d|i}\mu(d)=[i==1]$
$\therefore\sum\limits_{i=1}^n\sum\limits_{d|i}\mu(d)=1$
$\therefore\sum\limits_{i=1}^n\sum\limits_{j=1}^{\lfloor\frac{n}{i}\rfloor}\mu(j)=1$
$\therefore\sum\limits_{i=1}^nsum(\lfloor\frac{n}{i}\rfloor)=1$
$\therefore sum(n)+\sum\limits_{i=2}^nsum(\lfloor\frac{n}{i}\rfloor)=1$
$\therefore sum(n)=1-\sum\limits_{i=2}^nsum(\lfloor\frac{n}{i}\rfloor)$
然后我们发现，后面的$\lfloor\frac{n}{i}\rfloor$的取值是$\sqrt{n}$的。接下来就是比较蛇皮的地方了。
我们先预处理一段区间，然后对于每一个当前的n通过类似于记忆化爆搜的形式，如果当前访问sum是预处理范围之内的，我就直接返回，反之，通过同样的手段进行求解。这样，当预处理区间为$n^{\frac{2}{3}}$时，时间复杂度可以降至$O(n^{\frac{2}{3}})$。
挺伤心的，刚学Gauss消元上没有一些讲的比较详细的博客，尤其tm线性基。我找了挺久太(hua)(le)到一篇写的还okay的，稍微说一下什么是线性基和高斯消元。
首先，Gauss消元是一种求解多元线性方程组的问题（有没有和我一样想到CRT的），具体的实现非常的简单而且易懂。我们在求解二元一次方程组的时候，用加减消元或者行列式什么的瞎**搞就可以将它们解出或者得出无穷解或无解的结论。高斯消元也是同理，我们通过不断地加减消元：
首先，我们让每一个方程组都和第一个方程进行加减消元从而干掉第一个未知数，这样我们得到的n-1个方程就是n-1元的方程了。
同理，我们令第3个到第n个方程再与第2个方程进行加减消元干掉第二个未知量，注意，在这个过程中，由于我们已经将后面n-1个方程的第一个未知数都消掉了，所以第一个未知数不会“死而复生”，所以我们就会得到一个倒三角形状的方程组，其中，不断重复上面的操作可以知道第i个方程只有第i个到第n个未知数。
然后，最后一个方程显然只有一个未知数，所以我们只需要解出第n个未知数，不断往回代如求解即可。
这两步操作我们分别称之为“消去”和“回代”。这样就可以在$O(n^3)$的时间内求解n元1次方程组。
$M\ddot{o}bius$反演的证明(同届神犇要看)
在证明这个鬼东西之前，我们先说明几个东西。
首先，引入狄利克雷卷积。什么是狄利克雷卷积呢？就是说
函数f(n)，g(n)，那么，我们说函数$f\cdot g(n)=\sum\limits_{d|n}f(d)\cdot g(\frac{n}{d})$就是g(n)和f(n)的狄利克雷卷积。
它的最重要的性质：如果f(n)和g(n)都是积性函数，那么它们的狄利克雷卷积也是积性函数。第二个性质就是狄利克雷卷积满足结合律。
证一下结合律
$f\cdot g \cdot h(n) =\sum\limits_{lk=n}(f\cdot g(l))h(k)=\sum\limits_{lk=n}(\sum\limits_{ij=l}f(i)(j))h(k)=\sum\limits_{ijk=n}f(i)g(j)h(k)$，此时f,g,h是等势的，自然符合结合律。（其实此处也可以将$f\cdot (g \cdot h)(n)$也展开然后计算，只不过用等势证比较短）
然后，我们再引入几个函数
1.单位元函数$\iota(n)$，当n=1时$\iota(n)=1$，否则$\iota(n)=0$。显然，$f\cdot \iota(n)=\sum\limits_{d|n}f(d)\iota(\frac{n}{d})=f(n)$。
2.单位乘法常值函数$u(n)$，满足$u(n)=1$。
3.$\mu(n)$，$u(n)$在卷积定义下的逆元，即$u\cdot \mu=\iota$，这就是莫比乌斯函数的来源。通过这个，也极易验证原本的$M\ddot{o}bius$取值的定义的正确性。
$u\cdot \mu(n)=\sum\limits_{d|n}\mu(d)\cdot u(\frac{n}{d})=\sum\limits_{d|n}\mu(d)$
$n=p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k}$
$\sum\limits_{d|n}\mu(d)=\mu(1)+\mu(p_1)+\mu(p_2)+\cdots+\mu(p_k)+\mu(p_1p_2)+\cdots+\mu(p_1p_2...p_k)$
$\Rightarrow C_k^0+C_k^1(-1)+C_k^2(-1)^2+\cdots+C_k^k(-1)^k$
$\Rightarrow (1-1)^k=0$，显然n=0是原式为1，不在赘述。
然后，对于莫比乌斯反演的第一个反演
$F(n)=\sum\limits_{d|n}f(d)$，有$f(n)=\sum\limits_{d|n}F(d)\cdot \mu(\frac{n}{d})$。
怎么证呢？
显然：F的定义就相当于卷积中$F=f\cdot u$。
然后有$F\cdot \mu=f\cdot u \cdot \mu$。
由上文$\mu\cdot u=\iota$，可知$F\cdot \mu=f\cdot \iota$，这步应用了狄利克雷卷积的结合律。
紧接着，就有$F\cdot \mu=f$，因为任何的函数$g$都有$g\cdot \iota=g$，
这就证明了$f(n)=\sum\limits_{d|n}F(d)\mu(\frac{n}{d})$。
证毕。
$C_n^m=C_{\lfloor n/p\rfloor}^{\lfloor m/p\rfloor}\cdot C_{n _{mod}\;\;p}^{m_{mod}\;\;p}$
如何证明呢？先用几个引理。
引理一：$C_p^r\equiv0(mod\;p)$当且仅当$r\in [1,p-1]$。($p$为素数)
证明：显然。考虑组合数展开，分子上的$p!$中的素数p在分母中没有一个数可以将它消去，故此，证毕。
引理二：$(x+1)^p\equiv x^p+1(mod\;p)$。
证明：二项式定理展开后，对于任意的$i\in[2,p-1]$，$x^i$的系数都可以有引理一消去。所以，$LHS\equiv RHS$。证毕。
说完了引理，看一看卢卡斯。$C_n^m$是什么呢？就是在$(1+x)^n$中$x^m$的系数，那么我们将$n$欧基里德展开，可以得到$a$和$b$满足$a=n/p,b=n-p\cdot (\frac{n}{p})$
这样，我们就有$(x+1)^{ap}\cdot (x+1)^b$
$\Rightarrow ((x+1)^p)^a\cdot (x+1)^b$
运用刚刚证明的引理二
$\equiv (x^p+1)^a\cdot (x+1)b$
同样的，$c$和$d$是m的欧基里德展开结果。那么，我们考虑，$x^m=x^{cp}\cdot x^d$这一项中，$x^{cp}$显然只能从$(x^p+1)$获得，$x^d$只能从$(x+1)$得到贡献，所以就有在$(x+1)^p)^a$选取$c$个$(x+1)^p)$，另一侧选取$d$个。同样的又二项式定理，在$(x+1)^p)^a$中选取$c$个的方案数为$C_a^c$，另一侧为$C_b^d$，LHS的$x^m$的系数为$C_n^m$，$RHS$中$x^m$同样，只能是$C_a^c\cdot C_b^d$，所以$C_n^m\equiv C_a^c\cdot C_b^d(mod\;p)$，即
$C_n^m=C_{\lfloor n/p\rfloor}^{\lfloor m/p\rfloor}\cdot C_{n _{mod}\;\;p}^{m_{mod}\;\;p}$
证毕。
数论中的狗逼变换
1.欧拉函数应用。(神犇学长要求)
引进欧拉函数之前，我们先说一个东西：简化剩余系，俗称简系。n的简化剩余系就是%n的完全剩余系的一个极大子集，使得这其中的任意一个数k，有gcd(k%n,n)=1。我们记F为n的简系(没有特殊规定，仅在此篇blog下成立)，那么$\phi$(n)=|F|。这就是$\phi$(n)的定义。接下来，我们说几个欧拉函数的性质。
在证明之前，我们先说明：由于我们只考虑mod意义下，且是正整数范围，所以对于一个数n的完系我们不妨令其为正整数定义下最小完系，即{1,2,3,...,n-1}。
性质1：$\phi$(p)=p-1，p是素数。
证明：显然，1~p-1中的任意数i都有(i,p)=1，故$\phi$(p)=p-1。
性质2：n=$p^k$时，$\phi$(n)=(p-1)$\cdot p^(k-1)$。
证明：所有的非p的倍数均满足题意。
性质3：当gcd(n,m)=1时，$\phi$(nm)=$\phi$(n)*$\phi$(m)。
证明：$\phi$(n)是积性函数。
性质4：欧拉函数拆分，证明略。
性质5：欧拉定理，$a^{\phi(n)}\equiv1(mod\ m)$。
证明：由简系的正整数mod意义下唯一性可知，易知。
性质5.5：费马小定理。
证明：当欧拉定理的n是素数时即为欧拉定理。
性质6：正整数最小简系和为$n\cdot \frac{\phi(n)}{2}$。
证明：显然，简系中的数成对出现，证毕。
性质7：线筛欧拉函数。
证明：略。
以上是欧拉函数的基础知识，然后... ...
前几天考了一场试，全场没人切题，刚发道题就觉得自己Gg(实际Rank Sum20)，T1想到了一个贼神的正解(发现自己不会exgcd)，跟ljj说完了之后他说没懂... ...还好EF懂了，不然我都以为自己弄了一个傻逼算法... ...，被ljj当面推完exgcd之后没脸回去敲代码了，敲完了所有暴力挂了3个。20'就RankSum。(感觉自己最近话好多)
更一下T1的正解(没听懂我现场bb的可以在这重新看我bb一遍)
题目大意：给你一个正整数N，求所有的x$\in$[0,N]，满足$x^2\equiv1(mod\ N)$。
引理1：任意的正整数x,k,a；若满足x>k且x|a，则x$\not|$a$\pm$k。
证明：距离a最近的两个x的整数是a-x和a+x,而a-x < a-k < a < a+k < a+x，证毕。
引理2：任意的正整数x,k,a；若满足$x^k|a$且(k>1)，则$x||a\pm x$。
证明：不妨设$x^k||a$，则$a=x^k*C$，$a+x=x\cdot (x^{k-1}\cdot C+1)$，显然gcd($x^{k-1}\cdot C+1$,x)=1，证毕。
接下来，回到原题。$x^2\equiv1(mod\ N)$等价于N|(x-1)(x+1)显然的变换... ...
为了方便讨论，我们令a=x-1，原式等价于N|a(a+2)。
此时，我们将N用唯一分解定理分解。
$N=2^\alpha\cdot \sum\limits_{i=1}^{k}p_i^{\alpha_i}$，其中，p为严格递增奇素数数组。
那么，由引理1，对于每一个$p_i$来讲，满足$p_i$>2，那么如果$p_i$|a，那么$p_i\not|$a+2。反之同理。这意味着什么？意味着对于每一个奇素数来讲，只能有p|a或p|a+2，即每一个奇素数要么所有次幂都都被a分担，要么所有次幂都被a+2分担。我们设
n=$2^\alpha\cdot \sum\limits_{i=1}^{k}p_i^{\alpha_i}$，我们将n质因数分解之后，显然p最多有10个，此时我们二进制枚举。枚举哪些素数属于a，剩下的就由a+2分担。这样，我们将枚举的结果i，将i对应的$p^\alpha$全部乘到一起，设它等于s，剩下的就是t。s
和t满足gcd(s,t)=1，且s*t=n。
之后，我们在考虑2这个素数。有引理2，$2^{\alpha}$中，必须有a或a+2中的一个分担$2^{\alpha-1}$，剩下的只有一个2。这由引理2来讲是必然的。
不妨，我们就先假设由a来分担$2^{\alpha-1}$。
紧接着，我们就有两个式子：$2^{\alpha-1}\cdot s|a$，且$2t|a+2$。我们设正整数k和r。
满足：$2^{\alpha-1}\cdot sk==a$，且$2tr==a+2$
将第一个式子带入到第二个式子中，我们有：
$2tr==2^{\alpha-1}\cdot sk+2$
$\Leftrightarrow tr==2^{\alpha-2}\cdot sk+1$(此时，我们讨论$\alpha$是否大于1)
$\Leftrightarrow tr-2^{\alpha-2}\cdot sk==1$，此时我们已知$\alpha$，s和t。用exgcd就可以求出满足条件的k和r。(此处的条件意思是a有一个范围[0,N-1])
时间复杂度：首先，我们需要枚举a和a+2究竟是谁分担了$2^{\alpha-1}$，还有二进制枚举。
N的范围是$10^9$，所以奇质因子个数最多是9个，还有exgcd的log，所以总时间复杂度O(2^10logN)。
呼~
还没懂或者存在什么错误Qq联系我。2940699739
原题bzoj密码箱，用上述算法绰绰有余。
证明：$F_{gcd(x,y)}=gcd(F_x+F_y)$。其中，$F_i$表示第i个斐波那契数，其中，$F_1=1$，$F_2=1$。
我去？这玩意儿能对？其实能...我们来看题解证明一下
引理1：$gcd(F_{n+1},F_n)=1$，$1\le n$。
证明：显然，我们有：$gcd(F_{n+1},F_n)=gcd(F_n+F_{n-1},F_n)=gcd(F_{n-1},F_n)=...=gcd(F_2,F_1)=1$，证毕。
引理2：$F_{m+n}=F_mF_{n+1}+F_{m-1}F_n$，$n>0,m>0$。
证明：采用数学归纳法进行证明：
$Basic$：
当$n=1$时，$F_{m+1}=F_m+F_{m-1}$，因为$F_2=1$且$F_1=1$，
所以$F_{m+1}=F_mF_2+F_{m-1}F_1=F_mF_{n+1}+F_{m-1}F_n$。成立
当$n=2$时，$F_{m+2}=F_{m+1}+F_m=F_m+F_{m-1}+F_m=2*F_m+F_{m-1}=F_mF_3+F_{m-1}F2=F_mF_{n+1}+F_{m-1}F_n$。成立
$Induction$：
假设当$n=k$成立且$n=k-1$成立时，欲证明$n=k+1$成立。
$F_{m+k+1}=F_{m+k}+F_{m+k-1}=F_mF_{k+1}+F_{m-1}F_k+F_mF_k+F_{m-1}F_{k-1}=F_m*(F_{k+1}+F_k)+F_{m-1}*(F_k+F_{k-1})=F_mF_{k+2}+F_{m-1}F_{k+1}=F_mF_{n+1}+F_{m-1}F_n$，证毕。
引理3：$gcd(F_{m+n},F_n)=gcd(F_n,F_m)$。
证明：由引理2，$F_{m+n}=F_mF_{n+1}+F_{m-1}F_n$。
所以$gcd(F_{m+n},F_n)=gcd(F_mF_{n+1}+F_{m-1}F_n,F_n)$。
由引理1，$gcd(F_{n+1},F_n)=1$。所以$gcd(F_mF_{n+1},F_n)=gcd(F_m,F_n)$。证毕。
至此，我们发现了一件令人非常欣喜的事情：在$gcd$意义下的$F$满足辗转相除。
所以，因为gcd(i,j)=gcd(gcd(i,j),0)=gcd(i,j)，这看起来是一句废话，但是在当前的形势下却有这巨大的作用。
首先，欧几里得的辗转相除就是讲一个数消除掉另一个数的整数倍，这样，在当前形势下，每一次操作都可以用引理3来证明其正确性，即：欧几里得的辗转相除是可行的。
所以，我们有$gcd(F_x,F_y)=gcd(F_{gcd(x,y)},F_0)$。这是，因为$F_n=F_{n-1}+F_{n-2}$，所以$F_{n-2}=F_n-F_{n-1}$，所以$F_0=F_2-F_1=0$。
故$gcd(F_{gcd(x,y)},F_0)=F_{gcd(x,y)}$。
即：$gcd(F_x,F_y)=F_{gcd(x,y)}$。
证毕。
综上，这个证明并不是晦涩难懂的，但是这绝对不是一个容易的证明。首先，我们对$F$的了解本身就不熟悉，而且将两个函数的值的gcd跨越到两个数的gcd的函数值。这样的跨领域操作其实仔细揣摩好像只有欧几里得能干这事。
然后，在最后一步我们发现：这个结论并不是对所有的斐波那契都成立的。即对广义的$F_i=F_{i-1}+F_{i-2}$是不一定成立的，它的成立条件当且仅当$F_1==F_2$。其实具体的值倒是无所谓。
证一下exCRT吧，同届神犇342zhuyongqi要看。
首先我们都知道CRT的成立条件当且仅当所有的模数都互质，但是并不是所有的题目都可以保证这一点。
所以我们考虑如何在模数不互质的情况下求出满足条件的答案。
像CRT一样，我们考虑两个式子：
$x\equiv a_1(\%m_1)$，$x\equiv a_2(\%m_2)$
我们设$k_1$和$k_2$是满足$x=a_1+k_1m_1$和$x=a_2+k_2m_2$的两个整数。
显然我们有$a_1+k_1m_1=a_2+k_2m_2$
等价于$m_1k_1-m_2k_2=a_2-a_1$。
显然当$gcd(m_1,m_2)|a_2-a_1$时有解。
我们先将$m_1K_1-m_2K_2=gcd(m1,m2)$的解$K_1,K_2$算好。
紧接着将左右式子同时乘以$\frac{a_2-a_1}{gcd(m_1,m_2)}$就可以得到$k_1,k_2$。
有了$k_1,k_2$我们就可以得到x了。
但是怎么样才能求出x的通项呢？
我们设两个解为$x_0$和$x_1$。$(x_0<x_1)$
因为两个解都满足给定的两个同余方程
故此存在两个$\delta_1,\delta_2$满足：$x_1=x_0+\delta_1\times m_1$，$x_1=x_0+\delta_2\times m_2$。
我们设其中的$x1-x0$为$\Delta$
显然有$\delta_1\times m_1=\delta_2\times m_2$(1)。
设$d=gcd(m_1,m_2)$。$n_1=\frac{m_1}d，n_2=\frac{m_2}d$
(1)式等价于$\delta_1\times n_1d=\delta_2 \times n_2d$
$\Leftrightarrow \delta_1\times n_1=\delta_2\times n_2$
有$n_1|\delta_2\times n_2$。
由$n_1$和$n_2$的定义我们可以知道$gcd(n_1,n_2)=1$。
故此$n_1|\delta_2$。所以$n_1n_2|\delta_2\times n_2$
即$n_1\times n_2d|\delta_2\times n_2d$
进而$n_1\times n_2d|\Delta$。
而$n_1\times n_2d=\frac{n_1d\times n_2d}{d}=\frac{m_1\times m_2}{gcd(m_1,m_2)}=lcm(m_1,m_2)$。
故$lcm(m_1,m_2)|\Delta$。
所以我们得出：任意两个解之间的差都是模数的lcm倍。
又因为$x_0+A\times lcm(m_1,m_2)$显然都满足给定的两个同余方程。
所以通项就是任意解$x_0$加上任意倍的$lcm(m_1,m_2)$。
这样我们就将两个同余方程的通解得到了。
如果是多个方程的话两两合并即可。
证毕
原根与指标
定义：我们说原根啊，其实是针对模数的。
比方说就是模数$p$了。
那么$a$是$p$的原根，当且仅当$a$模$p$的阶是$\varphi(p)$。
言下之意就是$a$的$1$到$\varphi(p)$次幂构成了$p$的简系。
所谓指标呢？就是一个数$x$，其中$gcd(x,p)=1$，$a$是$p$的原根。
那么$ind(x)$就是$x$的指标，满足$a^{ind(x)}=x(mod\ p)$。
原根的求法：
一般呢，我们的办法都是枚举然后暴力验证。
但是当$p$是素数的时候我们有一个更好的办法：
如果当前枚举的数$a$满足任意的$p_i|p-1$，都有$a^{\frac{p-1}{p_i}}\% p$不等于$1$，那么$a$就是$p$的原根，反之不是。证明略。
例题时间~
题目大意：给定三个正整数$p$，$k$，$a$。其中$p$是质数，求所有满足条件的$x$：$x^k\equiv a(mod\ p)$，$0\le x\le p-1$。
注释：$2\le p\le int$，$0\le a < p$，$2\le k\le 10^5$。
题解：
我们看到这个式子容易看成$BSGS$裸题。但是$BSGS$是已知底数、余数和模数求指数，这个求底数。
这样的话我们想到求原根解决。
因为$p$是质数嘛，我们很容易就求出了$p$的原根$ori$。
接下来就是想到指标，我们设$ans$表示$ind(a)$。
这样的话我们就有：$x^k\equiv ori^{ans}(mod\ p)$。
等价于$ori^{ind(x)\cdot k}\equiv ori^{ans}(mod\ p)$。
等价于$ind(x)*k\equiv ans(mod\ \varphi(p))-----(1)$。
接下来就很明了了哦，我们就是要求所有的$ind(x)$，因为知道了$ori$和$ind(x)$就知道了$x$。
故此我们用$exgcd$先随便求出来一个$ind(x)$，设为$now$。
怎么求剩下的$ind(x)$呢？
我们看$(1)$式等价于$ind(x)\cdot k-\varphi (p)\cdot q = ans$。
由$Bezout$定理（裴蜀定理）可知所有的$ind(x)$都可以用$now+n\cdot \frac{\varphi(p)}{gcd(\varphi(p),k)}$表示。
这样我们就求出了所有的$ind(x)$，也就求出了所有的$x$。
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
#define N 1000010
using namespace std;
typedef long long ll;
map<ll,ll>MP;
ll prime[N],re[N];
ll qpow(ll x,ll y,ll mod)
{
ll ans=1;
while(y)
{
if(y&1) (ans*=x)%=mod;
y>>=1;
(x*=x)%=mod;
}
return ans;
}
void exgcd(ll X,ll Y,ll &x,ll &y,ll &d)
{
if(!Y){x=1;y=0;d=X;return ;}
exgcd(Y,X%Y,y,x,d);
y-=(X/Y)*x;
}
int main()
{
// freopen("1319.in","r",stdin);
// freopen("1319.out","w",stdout);
ll p,k,a,ori;
int tot=0,cnt=0;
scanf("%lld%lld%lld",&p,&k,&a);
if(!a) {puts("1"); puts("0"); return 0;}
k%=(p-1);
ll m=p-1;
for(int i=2;1ll*i*i<=m;i++)
{
if(m%i==0)
{
prime[++cnt]=i;
while(m%i==0) m/=i;
}
}
if(m!=1) prime[++cnt]=m;
for(int i=2;i<=p-1;i++)
{
bool flag=true;
for(int j=1;j<=cnt;j++) if(qpow(i,(p-1)/prime[j],p)==1)
{
flag=false;
break;
}
if(flag)
{
ori=i;
break;
}
}
// printf("Fuck %lld\n",ori);
ll q=ceil(sqrt(p));
ll now=1;
for(int i=1;i<=q;i++)
{
(now*=ori)%=p;
if(!MP[now]) MP[now]=i;
}
// (now*=ori)%=p;
ll sum=1;
ll ans;
for(int i=0;i<=q;i++)
{
ll mdl=a*qpow(sum,p-2,p)%p;
if(MP[mdl]) {ans=i*q+MP[mdl]; break;}
(sum*=now)%=p;
}
ll d=__gcd(k,p-1);
if(ans%d) puts("0"),exit(0);
ll X,Y,x,y,gcd;
X=k/d; Y=(p-1)/d;
exgcd(X,Y,x,y,gcd);
(x*=(ans/d))%=(p-1);
x%=Y;
if(x<=0) x+=Y;
while(x<=p-1)
{
re[++tot]=qpow(ori,x,p);
// re[++tot]=qpow(ori,x,p);
x+=Y;
}
cout << tot << endl ;
sort(re+1,re+tot+1);
for(int i=1;i<=tot;i++) printf("%lld\n",re[i]);
return 0;
}