积累一下见过或写过的快速幂

快速幂的思想就是对于一个数的偶数次幂可以把它分成一个数的平方，奇数次幂可以提出一个底数然后变成另一个数的平方。这样就能减少相乘的次数，比如原先要乘1024次的话现在只用乘10次。
对于x²ⁿ 只要计算出xⁿ就能直接平方的到答案，对于x²ⁿ⁺¹ 只要得到 xⁿ 就能直接平方再乘x的到答案，对于xⁿ的求法和x²ⁿ以及 x²ⁿ⁺¹相同。这样就能把O(n)的 时间复杂度降低到O(log n)了；

No.1

#define MOD 10000 //需要取模的值
long long quickpow(int x, int n) {
    long long ans = 1, t = x;
    while (n) {
        if (n & 1) ans = (long long) ans * t % MOD;
        t = (long long) t * t % MOD;
        n >>= 1;
    }
    return ans;
}

No.2

#define mod 10000 //需要取模的值
long long power(long long a,long long b)///a是底数，b是次幂
{
	long long ans=1;
	for(;b!=0;b>>=1)
	{
		if(b&1) ans=(long long)ans*a%mod;
		a=(long long)a*a%mod;
	}
	return ans;
}

No.3

欧拉降幂 a ^ b % mod = a ^ ( b % phi ( mod ) ) % mod，phi 就是 mod 的欧拉返回值，也就是1~mod中有多少个与mod互质的数
(白嫖我题的那个学长那里偷来的)

long long phi(long long n)   ///求欧拉函数值 返回值为多少个与n互质的数
{
    long long ans=n,temp=n;
    for(int i=2;i*i<=temp;i++)
    {
        if(temp%i==0)
        {
            ans-=ans/i;
            while(temp%i== 0) temp/=i;
        }
    }
    if(temp>1) ans-=ans/temp;
    return ans;
}