数学咋想 - 洛谷保存站

# 数学杂项

$1:{\Large a+a+a+a+...+a=a \times b}$  ( $b$ 为 $a$ 的个数）

$2:{\Large a \times a \times a \times a \times ... \times a=a^b}$  ( $b$ 为 $a$ 的个数）

## 快速幂！

${\Large Fristway} $ 
## 二分治

${\Large a^b=a^\frac{b}{2} \times a^\frac{b}{2} }$

代码如下：
```c
long long f(long long a,long long b,long long mod){
	if(b==1) return a;
	if(b%2==1){
		long long temp=f(a,b/2,mod);
		return temp*temp%mod*a%mod;
	}
	else{
		long long temp=f(a,b/2,mod);
		return temp*temp%mod;
	}
}
```

${\Large Secondway} $ 
## 倍增

代码如下：

```cpp
long long ksm(long long a,long long b,long long mod){
	long long ans=1;
	while(n){
		if(n%2==1)
			ans=ans*m%mod;
		m=m*m%mod;
		n/=2;
	}
	return ans;
}
```
		
## 肥妈（费马）小定理	$(p$ $is$ $prime)$

$a^{p-1} \equiv 1(mod$ $p)$

$\therefore a^{p-2} \times a \equiv 1(mod$ $p)$

$\therefore a^{p-2} \equiv \frac{1}{a}(mod$ $p)$

$\therefore a^{b} \equiv a^{b\ mod\ (p-1)}(mod$ $p)$

## 欧拉函数：$\varphi(n)=\sum_{i=1}^{n}[\gcd(i,n)=1]$ $(p$ $is$ $prime)$

~~(orz 欧拉大佬)~~

## SO 欧拉 creat that $(p$ $is$ $prime)$

$\large a^{b} \equiv\left\{\begin{matrix}b<\varphi(n) \Rightarrow
  & a^{b} \\b>\varphi(n) \Rightarrow
  &a^{b \mod \varphi(p)~+~\varphi(n)}
\end{matrix}\right. (mod$ $p)$

$\large a^ {\varphi(p)}\equiv 1$

$\large \varphi (p)=p \times a \prod_{i=1}^{k} \frac{(p_i=i)}{p_i} $

$\large p=\prod_{i=1}^{k}{p_i}^{k_i}$

求欧拉函数代码：

```
int phi(int n){
	int ans=n;
	for(int i=2;i<=n/i;i++){
		if(n%i==0){
			ans=ans/i*(i-1);
			while(n%i==0){
				n/=i;
			}
		}
	}
	if(n!=0){
		ans=ans/n*(n-1);
	}
	return ans;
}
```

$ \sum_{i=1}^{n}i =\frac{(n+1)n}{2} $

$ \sum_{i=1}^{n}i^2 =\frac{(2n+1)(n+1)n}{6} $

$ \sum_{i=1}^{n}i^3 =(\frac{(n+1)*n}{2})^2$

正在渲染内容...