11.23

数论

---欧几里得，埃拉托色尼筛，二分快速幂，同余定理

欧几里得，每一次递归，返回的就是由最后一次递归计算出的结果

#include <stdio.h>
int gcd(int n,int m)
{
    if (m == 0)
        return n;
    else
        return gcd(m,n % m);
}
int main(void)
{
    int a,b;
    int ans;
    scanf("%d%d",&a,&b);
    ans = gcd(a,b);
    printf("%d\n",ans);
    return 0;
}

强大的埃拉托色尼筛，思想就是把所有素数的倍数标记为0：

#include <stdio.h>
#include <math.h>
#define n 10005
int a[n];
int main(void)
{
    int i,j;
    for (i = 2;i <= n;i++)
        a[i] = 1;
    for (i = 2;i <= sqrt(n);i++)
    {
        if (a[i])
        {
            for (j = 2;i * j <= n;j++)
                a[i*j] = 0;
        }
    }
    for (i = 2;i <= n;i++)
        if (a[i])
            printf("%4d ",i);
    return 0;
}

二分快速幂 + 同余定理：
拆分的思想，但是拆分是有规律的。
至于同余定理，则是(a*b) mod m = (a mod m) * (b mod m),加法是每加一次，膜一次（蛤。减法是给被减数加上m之后先算减法，后算 mod m。
求m的n次方：

#include <stdio.h>
const long long t = 1000000007;
long long _pow(long long x,long long n)
{
    if (n == 0)
        return 1;
    else if (n % 2 == 0)
        return _pow(x*x,n / 2) % t;
    else
        return _pow(x*x,n / 2) * x % t;
}
int main(void)
{
    int x,n;
    long long ans = 0;
    scanf("%d%d",&x,&n);
    ans = _pow(x,n);
    printf("%I64d\n",ans);
    return 0;
}