【疯狂gcd】的推式子过程

${\sum }_{i=1}^n{\sum }_{j=1}^{n}gcd(i,j)$

$=2{\sum }_{i=1}^n{\sum }_{j=1}^{i}gcd(i,j)-{\sum }_{1=1}^{n}i$

$f(n)={\sum }_{j=1}^{n}gcd(n,j)$

$f(n)={\sum }_{d|n}d{\sum }_{i=d,d|i}^n[gcd(i,n)==d]$

（令$i=jd$）

$f(n)={\sum }_{d|n}d{\sum }_{j=1}^{\frac{n}{d}}[gcd(j,\frac{n}{d})==1]$

$f(n)={\sum }_{d|n}d\phi (\frac{n}{d})$

${\sum }_{i=1}^n{\sum }_{j=1}^{i}gcd(i,j)$

$={\sum }_{i=1}^n{\sum }_{d|i}d\phi (\frac{i}{d})$

$={\sum }_{d=1}^{n}d{\sum }_{i=1,d|i}^n\phi (\frac{i}{d})$

（令$i=jd$）

$={\sum }_{d=1}^{n}d{\sum }_{j=1}^{\lfloor \frac{n}{d}\rfloor }\phi (j)$

exgcd

$ax+by=1$

$b{x}^{\prime }+(a\mathrm{m}\mathrm{o}\mathrm{d}b)y^{\prime }=1$

即$b{x}^{\prime }+(a-kb)y^{\prime }=1$

其中，$k=\lfloor \frac{a}{b}\rfloor$。

$a{y}^{\prime }+b(x^{\prime }-k{y}^{\prime })=1$

$x^{\prime },y^{\prime }$已知（最后一步是$x^{\prime }=1,y^{\prime }=0$，递归推导前面的$x$和$y$）

$x=y^{\prime },y=x^{\prime }-k{y}^{\prime }$

void exgcd(int a,int b,int& x,int& y){
   
    if(!b){
   x=1,y=0;return;}
    exgcd(b,a%b,x,y);
    int xx=x,yy=y;
    x=yy,y=xx-a/b*yy;
    //简便但不是很容易理解的写法：exgcd(b,a%b,y,x),y-=a/b*x;
}

exCRT

前面几个方程解出的结果为：$x=A\mathrm{m}\mathrm{o}\mathrm{d}M$

新的方程：$x=a\mathrm{m}\mathrm{o}\mathrm{d}m$

设：

$x=A+M{y}_1$

$x=a+m{y}_2$

两式相减：

$M{y}_1-m{y}_2=a-A$

$M{y}_1=a-A\mathrm{m}\mathrm{o}\mathrm{d}m$

设$d=\gcd (M,m)$

$\frac{M}{d}{y}_1=\frac{a-A}{d}\mathrm{m}\mathrm{o}\mathrm{d}\frac{m}{d}$

$\text{exgcd}$解出$y_1$后得

$x=A+M{y}_1\mathrm{m}\mathrm{o}\mathrm{d}lcm(M,m)$

int n;
ll exgcd(ll a,ll b,ll& x,ll& y){
   
	if(!b)return x=1,y=0,a;
	ll d=exgcd(b,a%b,y,x);
	y-=x*(a/b);
	return d;
}
int main(){
   
	while(~scanf("%d",&n)){
   
		ll M=read(),x0=read(),mi,ai,c,t;
		for(int i=2;i<=n;++i){
   
			ll mi=read(),ai=read(),x,y;
			if(x0==-1)continue;
			ll c=(ai-x0%mi+mi)%mi,d=exgcd(M,mi,x,y);
			ll t=mi/d;
			if(c%d){
   x0=-1;continue;}
			x=(__int128)x*c/d%t;
			x0+=M*x,M*=t,x0=(x0%M+M)%M;
		}
		enter(x0);
	}
}

BSGS

$g^x=a\mathrm{m}\mathrm{o}\mathrm{d}p$

令$k=\lfloor \sqrt p\rfloor $

$mp[g^i\mathrm{m}\mathrm{o}\mathrm{d}p]=i$（$0\le i\le k,mp$是一个map容器）

枚举$i$，计算$a\times g^{-ik}\mathrm{m}\mathrm{o}\mathrm{d}p$

若存在$j$，使$mp[a\times g^{-ik}\mathrm{m}\mathrm{o}\mathrm{d}p]=j$，则$a\times g^{-ik}=g^j\mathrm{m}\mathrm{o}\mathrm{d}p$，即$a=g^{ik+j}\mathrm{m}\mathrm{o}\mathrm{d}p$。

即$x=ik+j$。

${\sum }_{i=1}^n{i}^k$

${\sum }_{i=1}^n{i}^4$？？？

$1^5-0^5+2^5-1^5+\cdots +n^5-(n-1{)}^5=n^5$

$n^5={\sum }_{i=1}^n{i}^5-{\sum }_{i=1}^n(i-1{)}^5$

$={\sum }_{i=1}^n{i}^5-{\sum }_{i=1}^n(i^5-C_5^1{i}^4+C_5^2{i}^3-C_5^3{i}^2+C_5^{4}i-1)$

$=C_5^1{\sum }_{i=1}^n{i}^4-C_5^2{\sum }_{i=1}^n{i}^3+C_5^3{\sum }_{i=1}^n{i}^2-C_5^4{\sum }_{i=1}^{n}i+1$

${\sum }_{i=1}^n{i}^4=\frac{n^5+C_5^2{\sum }_{i=1}^n{i}^3-C_5^3{\sum }_{i=1}^n{i}^2+C_5^4{\sum }_{i=1}^{n}i-1}{5}$

一般地：

${\sum }_{i=1}^n{i}^k=\frac{n^{k+1}+{\sum }_{j=2}^k{C}_{k+1}^j(-1{)}^j{\sum }_{i=1}^n{i}^{k+1-j}}{k+1}$