模板

矩阵快速幂（专门针对于斐波那契数列的模板）

__int64 fast_mod(__int64 n)    // 求 (t^n)%MOD
{
   __int64 t[2][2] = {1, 1, 1, 0};
    __int64 ans[2][2] = {1, 0, 0, 1};  // 初始化为单位矩阵
    __int64 tmp[2][2];    //自始至终都作为矩阵乘法中的中间变量

    while(n)
    {
        if(n & 1)  //实现 ans *= t; 其中要先把 ans赋值给 tmp，然后用 ans = tmp * t
        {
            for(int i = 0; i < 2; ++i)
                for(int j = 0; j < 2; ++j)
                    tmp[i][j] = ans[i][j];
            ans[0][0] = ans[1][1] = ans[0][1] = ans[1][0] = 0;  // 注意这里要都赋值成 0

            for(int i = 0; i < 2; ++i)    //  矩阵乘法
            {
                for(int j = 0; j < 2; ++j)
                {
                    for(int k = 0; k < 2; ++k)
                        ans[i][j] = (ans[i][j] + tmp[i][k] * t[k][j]) % MOD;
                }
            }
        }

        //  下边要实现  t *= t 的操作，同样要先将t赋值给中间变量  tmp ，t清零，之后 t = tmp* tmp
        for(int i = 0; i < 2; ++i)
            for(int j = 0; j < 2; ++j)
                tmp[i][j] = t[i][j];
        t[0][0] = t[1][1] = 0;
        t[0][1] = t[1][0] = 0;
        for(int i = 0; i < 2; ++i)
        {
            for(int j = 0; j < 2; ++j)
            {
                for(int k = 0; k < 2; ++k)
                    t[i][j] = (t[i][j] + tmp[i][k] * tmp[k][j]) % MOD;
            }
        }
        n >>= 1;
    }
    return ans[0][1];
}

欧拉函数（小于等于N的且与N互质的数的个数）

int  p[ maxn   ];
    long long   phi[ maxn + 1];
    long long i,j;
    for(i = 1; i <= maxn; i++)    // 初始化
    { p[i] = 1; phi[i] = i; }
    p[1] = 0;    // 1不是素数
    for(i = 2; i<= maxn; i++)    // 筛素数
    {
        if(p[i])
        {
            for(j = i * i; j <= maxn; j += i)
            { p[j] = 0; }
        }
    }
    for(i = 2; i <= maxn; i++)    // 求欧拉函数
    {
        if(p[i])
        {
            for(j = i; j <= maxn; j += i)    // 处理素因子p[i]
            {
                phi[j] = phi[j] / i * (i - 1);    // 先除后乘，防止中间过程超出范围
            }
        }
    }